题意

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入 #1

5 5
1 1 1 1 1

输出 #1

5

样例解释 #1

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

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

输入 #2

6 4
1 2 1 1 2 2

输出 #2

0

样例解释 #2

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

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

输入 #3

7 3
3 7 9 1 7 5 3

输出 #3

23

样例解释 #3

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

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

输入 #4

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

输出 #4

71

样例解释 #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)$。

$$ \begin{array}{|c|c|c|} \hline \textbf{Subtask} & \textbf{特殊性质} & \textbf{Score} \\ \hline 1 & N = K & 30 \\ \hline 2 & A_i \le 2 & 25 \\ \hline 3 & A_i \textbf{均为奇数} & 20 \\ \hline 4 & \textbf{无} & 25 \\ \hline \end{array} $$

本题 Subtask 内捆绑测试。