题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day2 T2. Пари камінців

爱丽丝和鲍勃有 $n$ 堆石子，编号从 $1$ 到 $n$。第 $i$ 堆有 $a_i$ 个石子。他们进行以下过程：

1. 爱丽丝选择两堆非空的石子堆，假设这两堆分别有 $x$ 和 $y$ 个石子。
2. 爱丽丝从这两堆石子中各取走一个石子。
3. 接着，鲍勃也选择两堆非空的石子堆，要求这两堆分别有 $x$ 和 $y$ 个石子，即鲍勃选择的石子堆数量必须与爱丽丝最初选择的石子堆数量相同。鲍勃可以选择与爱丽丝相同的石子堆。如果他无法做到这一点，过程结束。
4. 鲍勃也从他选择的这两堆石子中各取走一个石子。
5. 如果非空石子堆的数量小于 $2$，则过程结束；否则，回到第一步重新开始。

请注意，爱丽丝不必每次都选择相同的 $x$ 和 $y$ 值。

爱丽丝和鲍勃希望最终石子堆中剩余的石子数量尽可能少。注意，他们有共同的目标。请帮助他们找出可能的最小剩余石子数量。

输入格式

第一行包含两个整数 $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})$，表示每堆石子的数量。

输出格式

输出一个整数，表示任务的答案，即最终可能的最小剩余石子数量。

3 0
4 4 3

5

在第一个样例中，爱丽丝可以先选择第一堆和第三堆：$x=4$ 和 $y=3$。在她取走石子后，石子堆变为 $3, 4, 2$。

鲍勃必须选择两堆分别有 $x=4$ 和 $y=3$ 个石子的堆，因此他会选择第二堆和第一堆。在他取走石子后，石子堆变为 $2, 3, 2$。

下一步，爱丽丝可以选择第二堆和第三堆：$x=3$ 和 $y=2$。在她取走石子后，石子堆变为 $2, 2, 1$。

鲍勃无法选择两堆分别有 $x=3$ 和 $y=2$ 个石子的堆，因此过程结束。最终剩余石子数量为 $2+2+1=5$。

7 0
4 7 7 4 2 2 3

3

数据范围与提示

详细子任务附加限制及分值如下表所示：