P12074 [OOI 2025] The arithmetic exercise

[试题来源](https://inf-open.ru/2024-25/final-materials/)。

Oleg 和 Dasha 参加了一场团队竞赛，但不幸的是，他们未能解决任何问题。Oleg 立刻意识到他们的队伍训练不足。然后，他们共同的朋友提出了一个有趣的练习。这个练习相当简单，要解决它，只需要知道整数加减法的规则。 给定一个长度为 $n$ 的数组 $a$，初始时所有值均为零。同时给定 $m$ 个数 $x_1, x_2, \ldots, x_m$。然后，对于从 $1$ 到 $m$ 的每个 $i$，你需要选择某个下标 $j_i$，并执行更改 $a_{j_i} = x_i - a_{j_i}$。 请帮助 Oleg 和 Dasha 确定，如果每次选择都最优，那么在所有更改完成之后，数组 $a$ 的元素之和的最大值可能为多少。

每个测试包含多个输入数据集。第一行包含一个整数 $t$（$1 \le t \le 10\,000$）—— 输入数据集的数量。 每个数据集的第一行包含两个整数 $n$ 和 $m$。（$1 \le n, m \le 300\,000$） 每个数据集的第二行包含 $m$ 个整数 $x_1, x_2, \ldots, x_m$。（$-10^9 \le x_i \le 10^9$） 设 $N$ 为所有数据集中 $n$ 的总和，$M$ 为所有数据集中 $m$ 的总和。 保证 $N$ 和 $M$ 均不超过 $300\,000$。

对于每个数据集，在新的一行输出一个数字 —— 可以得到的数组 $a$ 的和的最大值。

**样例解释** 在第一个数据集中，所有操作都应用于数组 $a$ 的第一个元素。它依次变为 $1 - 0 = 1$，$2 - 1 = 1$，$3 - 1 = 2$，$4 - 2 = 2$，所以答案是 $2$。 在第二个数据集中，可以执行以下更改序列： 1. 将更改应用于第一个元素：$a_1 = 10 - a_1 = 10 - 0 = 10$，此时 $a = [10, 0]$。 2. 将更改应用于第一个元素：$a_1 = 3 - a_1 = 3 - 10 = -7$，此时 $a = [-7, 0]$。 3. 将更改应用于第一个元素：$a_1 = 7 - a_1 = 7 - (-7) = 14$，此时 $a = [14, 0]$。 4. 将更改应用于第一个元素：$a_1 = 1 - a_1 = 1 - 14 = -13$，此时 $a = [-13, 0]$。 5. 将更改应用于第二个元素：$a_2 = 4 - a_2 = 4 - 0 = 4$，此时 $a = [-13, 4]$。 6. 将更改应用于第一个元素：$a_1 = 6 - a_1 = 6 - (-13) = 19$，此时 $a = [19, 4]$。 7. 将更改应用于第二个元素：$a_2 = 3 - a_2 = 3 - 4 = -1$，此时 $a = [19, -1]$。 最后，我们得到 $a = [19, -1]$，所以最终的和是 $18$。 可以证明不可能得到更好的结果。 **评分** 本题的测试点包含十个分组。每个分组的分数只有在该分组的所有测试点以及所有依赖分组的测试点都通过时才能获得。请注意，通过样例测试点对于某些分组不是必需的。**Offline-evaluation** 表示该分组的测试结果将在比赛结束后才可查看。 | Subtask | 分数 | 额外限制：$n, N$ | 额外限制：$m, M$ | 额外限制：$x_i$ | 依赖组别 | 说明 | | :--- | :--- | :--------------- | :--------------- | :--------------- | :------- | :--------------------------------------------------- | | 0 | 0 | -- | -- | -- | -- | 样例。 | | 1 | 4 | -- | -- | $0 \le x_i$ | -- | 所有 $x_i$ 都相同。 | | 2 | 8 | $n=2$ | $M \le 30$，$m \le 18$ | -- | -- | | | 3 | 11 | $n=2$ | $M \le 50$ | $-10 \le x_i \le 10$ | -- | | | 4 | 9 | $n=2$ | $M \le 400$ | $-400 \le x_i \le 400$ | 3 | | | 5 | 8 | $N \le 30$，$n \le 18$ | $M \le 30$，$m \le 18$ | -- | 0 | | | 6 | 10 | $N \le 2000$ | $M \le 2000$ | $0 \le x_i$ | -- | | | 7 | 12 | $N \le 2000$ | $M \le 2000$ | -- | 0, 2 -- 6 | | | 8 | 10 | -- | -- | $0 \le x_i$ | 1 | $x_i$ 中最多只有两个不同的值。 | | 9 | 17 | -- | -- | $0 \le x_i$ | 1, 6, 8 | | | 10 | 11 | -- | -- | -- | 0 -- 9 | **Offline-evaluation**。 |