算术练习

• 输入文件：标准输入
• 输出文件：标准输出
• 时间限制：2 秒
• 内存限制：256 MB

---

题目描述

Oleg 和 Dasha 参加了一项团队竞赛，但遗憾的是，他们没有解出任何题目。Oleg 立刻意识到他们的团队训练不足。于是，他们的一个共同朋友提出了一项有趣的练习。这项练习并不难，只需要知道整数的加法和减法规则即可。

你有一个长度为 $n$ 的数组 $a$，初始时所有元素均为 $0$。
你还得到 $m$ 个数 $x_1, x_2, \ldots, x_m$。
然后，对于 $i$ 从 $1$ 到 $m$，你依次选择一个下标 $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$）——数组 $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 \le 300\,000$。

---

输出格式

对于每个测试用例，输出一行一个整数——能够获得的最大数组元素和。

---

示例

标准输入

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

---

样例解释

第一个测试用例

所有操作都作用在数组的第一个元素上，依次得到：
$1 - 0 = 1$，$2 - 1 = 1$，$3 - 1 = 2$，$4 - 2 = 2$，最终答案为 $2$。

第二个测试用例

一种最优操作序列（数组初始 $[0, 0]$）：

1. 作用在第 1 个元素：$a_1 = 10 - 0 = 10$ → $[10, 0]$
2. 作用在第 1 个元素：$a_1 = 3 - 10 = -7$ → $[-7, 0]$
3. 作用在第 1 个元素：$a_1 = 7 - (-7) = 14$ → $[14, 0]$
4. 作用在第 1 个元素：$a_1 = 1 - 14 = -13$ → $[-13, 0]$
5. 作用在第 2 个元素：$a_2 = 4 - 0 = 4$ → $[-13, 4]$
6. 作用在第 1 个元素：$a_1 = 6 - (-13) = 19$ → $[19, 4]$
7. 作用在第 2 个元素：$a_2 = 3 - 4 = -1$ → $[19, -1]$

最终和为 $19 + (-1) = 18$，可以证明无法得到更大的和。

---

评分规则

测试数据分为 $10$ 组。只有通过某组的所有测试以及它依赖的前若干组的所有测试，才能获得该组分数。
注意：通过题目描述中的样例不是某些组的前置条件。
“离线评测”表示该组的结果仅在比赛结束后才能看到。
每组最终得分为所有提交中在该组获得的最高分。

组号	分值	额外限制	依赖组	备注
0		–	–	题目中的样例
1	4	$n$ 任意，$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$，$x_i$ 中至多两个不同的值	1
9	17	$0 \le x_i$	1, 6, 8
10	11	–	0–9	离线评测