AT_joig2025_a カードゲーム 4 (Card Game 4)

有 $N$ 张编号从 $1$ 到 $N$ 的卡片，每张卡片上写有一个整数，卡片 $i$（$1 \leq i \leq N$）上写的整数为 $A_i$。 你需要从这 $N$ 张卡片中选择 $K$ 张。如果所选的 $K$ 张卡片上的整数的奇偶性完全相同，那么你的得分为所选 $K$ 张卡片上的整数之和；否则，得分为 $0$。 给定所有卡片上的数字信息，请编写程序求出你能够获得的最大可能得分。

输入格式如下： > $N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

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

## 子任务 1. （$30$ 分）$N=K$。 2. （$25$ 分）$A_i \leq 2$（$1 \leq i \leq N$）。 3. （$20$ 分）$A_i$ 全为奇数（$1 \leq i \leq N$）。 4. （$25$ 分）无额外限制。 ## 样例解释 1 考虑选择卡片 $1,2,3,4,5$，这时选择的卡片上的数字全为奇数，因此得分为 $1+1+1+1+1=5$。 在所有选法中，没有能得到 $6$ 或以上分数的方法。因此应输出 $5$。 这个输入样例满足所有子任务的限制。 ## 样例解释 2 无论你如何选择 $K$ 张卡片，得分都为 $0$。因此应输出 $0$。 这个输入样例满足子任务 $2,4$ 的限制。 ## 样例解释 3 考虑选择卡片 $1,2,6$，这时选择的卡片上的数字全为奇数，因此得分为 $3+7+5=15$。 考虑选择卡片 $2,3,5$，这时选择的卡片上的数字全为奇数，因此得分为 $7+9+7=23$。 在所有选法中，没有能得到 $24$ 或以上分数的方法。因此应输出 $23$。 这个输入样例满足子任务 $3,4$ 的限制。 ## 样例解释 4 这个输入样例满足子任务 $4$ 的限制。 ## 数据范围 - $1 \leq N \leq 100\,000$。 - $1 \leq K \leq N$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - 所有输入的数都是整数。 由 ChatGPT 5 翻译