P12638 [UOI 2020] Stone Pairs

Alice 和 Bob 有 $n$ 堆石子，编号从 $1$ 到 $n$。第 $i$ 堆石子有 $a_i$ 颗。他们执行以下过程： - Alice 选择两堆非空的石子堆，假设这两堆分别有 $x$ 和 $y$ 颗石子。 - Alice 从这两堆中各取走一颗石子。 - 接着，Bob 也必须选择两堆非空的石子堆，且这两堆的石子数量必须与 Alice 最初选择的两堆相同（即分别为 $x$ 和 $y$ 颗）。Bob 可以选择 Alice 选过的石堆。如果他无法选择这样的两堆，则过程结束。 - Bob 从他选择的两堆中各取走一颗石子。 - 如果非空的石子堆数量少于 $2$，则上述过程结束，否则重复从第一步开始。 注意 Alice 每次可以选择不同的 $x$ 和 $y$ 值。 Alice 和 Bob 希望最终剩下的石子尽可能少。注意他们的目标是共同的。请帮助他们求出最终可能剩下的最少石子数量。

第一行包含两个整数 $n$ 和 $g$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq g \leq 5$）——石子堆的数量和测试组编号。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——每堆石子的初始数量。

输出一个整数——最终剩下的最少石子数量。

在第一个样例中，Alice 可以先选择第一堆和第三堆：$x=4$ 和 $y=3$。取走石子后，三堆的石子数量分别为 $3$、$4$、$2$。 Bob 必须选择石子数量为 $x=4$ 和 $y=3$ 的两堆，因此他会选择第二堆和第一堆。取走石子后，三堆的石子数量分别为 $2$、$3$、$2$。 在下一步中，Alice 可以选择第二堆和第三堆：$x=3$ 和 $y=2$。取走石子后，三堆的石子数量分别为 $2$、$2$、$1$。 Bob 无法找到石子数量为 $x=3$ 和 $y=2$ 的两堆，因此过程结束。最终剩下的石子总数为 $2+2+1=5$。 ### 评分标准 - （$17$ 分）$n \leq 8$；$a_i \leq 8$； - （$23$ 分）$n$ 为偶数；$a_1=a_2$，$a_3=a_4$，$\dots$，$a_{n-1}=a_{n}$； - （$22$ 分）所有 $a_i$ 均为偶数； - （$18$ 分）$a_i \leq 2 \cdot 10^5$； - （$20$ 分）无额外限制。 翻译由 DeepSeek V3 完成