该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $N$ 张卡牌，编号为 $1$ 到 $N$，卡牌 $i(1\le i\le N)$ 上写有一个整数 $A_i$。

现在需要从 $N$ 张卡牌中选择 $K$ 张；对于一种选择，你的得分按照如下的方式进行计算：

• 如果选择的卡牌上写有的整数奇偶性两两相同，那么分数为你选择的所有卡牌上写有的整数之和；
• 否则分数为 $0$。

请求出你能获得的最大得分。

输入格式

第一行输入两个整数 $N,K$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一行一个整数，表示最大得分。

5 5
1 1 1 1 1

5

6 4
1 2 1 1 2 2

0

7 3
3 7 9 1 7 5 3

23

10 3
23 19 21 20 22 18 22 22 24 27

71

提示

样例 1 解释】

只有一种选择方案，即选择所有的卡牌；由于选择的卡牌上写有的整数均为奇数，故得分为 $1+1+1+1+1=5$。

该样例满足所有子任务的限制。

样例 2 解释

无论你如何选择 $K=4$ 张卡牌，你的得分都是 $0$。

该样例满足子任务 $2,4$ 的限制。

样例 3 解释

• 其中一种方案为选择卡牌 $1,2,6$，由于选择的卡牌上写有的整数均为奇数，得分为 $3+7+5=15$，但不是最优的；
• 最优方案为选择卡牌 $2,3,5$，由于选择的卡牌上写有的整数均为奇数，得分为 $7+9+7=23$。

该样例满足子任务 $3,4$ 的限制。

样例 4 解释

该样例满足子任务 $4$ 的限制。

数据范围

对于 $100\%$ 的数据满足：

• $1\le N\le 10^5$；
• $1\le K\le N$；
• $1\le A_i\le 10^9(1\le i\le N)$。