Polycarp 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
他想用这个数组玩一个游戏。游戏由几个动作组成。在第一次移动时,他选择任何元素并将其删除(第一次移动后,数组包含 $$$n-1$$$ 元素)。对于接下来的每次移动,他选择具有唯一限制的任何元素:其奇偶校验应该与上一步删除的元素的奇偶校验不同。换句话说,他交替删除的元素的奇偶性(偶-奇-偶-奇-...或奇-偶-奇-偶-...)。如果波利卡普无法采取行动,他就会停下来。
正式:
- 如果是第一步,他选择任意元素并将其删除;
- 如果是第二步或任何下一步:如果最后删除的元素是奇数,波利卡普选择任何偶数元素并将其删除; 如果最后删除的元素是偶数,则 Polycarp 选择任何奇数元素并将其删除。
- 如果经过一段移动后波利卡普无法移动,则游戏结束。
Polycarp 的目标是在游戏结束后最小化数组中未删除元素的总和。如果 Polycarp 可以删除整个数组,则未删除元素的总和为零。
帮助 Polycarp 找到这个值。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — $$$a$$$ 的元素数量。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。
输出
打印一个整数——游戏结束后数组中未删除元素的最小可能总和。
示例
输入 #1
5 1 5 7 8 2
输出 #1
0
输入 #2
6 5 1 2 4 6 3
输出 #2
0
输入 #3
2 1000000 1000000
输出 #3
1000000