题目描述

有 $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$ 的限制。

【数据范围】

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

【子任务】

1. （$30$ 分）$N=K$；
2. （$25$ 分）$A_i\le 2(1\le i\le N)$；
3. （$20$ 分）$A_i$ 均为奇数 $(1\le i\le N)$；
4. （$25$ 分）无附加限制。