← 返回题目列表

Codeforces · 1144/B

B. 奇偶校验交替删除

中文机器翻译题面 查看原题

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