第 4 题 算术练习 (thearithmeticexercis)

CSP-S 复赛模拟赛 22 · 时间限制 2 s · 空间限制 256 MB · 79 个测试点 · 特殊 Judge

本题使用文件输入输出：输入文件 thearithmeticexercis.in，输出文件 thearithmeticexercis.out。

时间限制：2 秒 内存限制：256 MB

题目描述

奥列格和达莎参加了一场团队比赛，但遗憾的是他们一道题也没能做出来。奥列格立刻意识到他们的队伍训练不足。于是他们共同的朋友提出了一个有趣的练习。这个练习相当简单，要解决它只需要知道整数加减法的规则。

给定一个长度为 $n$ 的数组 $a$，最初所有值都是零。另外给定 $m$ 个数 $x_1, x_2, \ldots x_m$。然后，对每个 $i$ 从 $1$ 到 $m$，你选择一个下标 $j_i$ 并执行修改 $a_{j_i} = x_i - a_{j_i}$。

请帮助奥列格和达莎确定，在所有修改完成后，如果选择方式最优，数组 $a$ 的元素之和最大可能是多少。

输入格式

每组测试包含若干组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10\,000$）——输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300\,000$）——数组 $a$ 的长度，以及数值 $x_i$ 的个数。

每组数据的第二行包含 $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$ 的最大元素之和。

样例

样例 1

输入：

4
1 4
1 2 3 4
2 7
10 3 7 1 4 6 3
4 10
103 354 1 227 179 189 142 201 165 140
5 3
-10 11 -4

输出：

2
18
1085
17

提示

样例解释

第一组数据中，所有操作都作用在数组 $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。

可以证明不可能得到更好的结果。

约束与子任务

本题的测试点分为十组。只有当该组的所有测试点以及所有所需组的测试点都通过时，该组的分数才会被计入。请注意：对某些组而言，通过样例测试并不是必需的。离线评测意味着你的程序在该组上的评测结果只有在比赛结束后才能获知。