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 翻译