题目描述

题目译自 Open Olympiad in Informatics 2025 Day1 T2 「Арифметическое упражнение / The arithmetic exercise」。

奥列格和达莎参加了一场团队奥林匹克竞赛，但遗憾的是他们未能解决任何问题。奥列格很快意识到他们的团队缺乏足够的训练。这时，他们的一位共同朋友向他们推荐了一项有趣的练习。这项练习并不复杂，只需掌握整数的加减法规则即可完成。

给定一个长度为 $n$ 的数组 $a$，初始时所有元素均为 $0$。同时给定 $m$ 个数字 $x_1, x_2, \ldots, x_m$。接下来，你需要依次对每个 $i$（从 $1$ 到 $m$）选择一个编号 $j_i$，并执行操作 $a_{j_i} = x_i - a_{j_i}$。

请帮助奥列格和达莎计算，在所有操作完成后，通过最优选择编号 $j_i$，数组 $a$ 的元素之和的最大值是多少。

输入格式

每个测试点包含多组输入数据。第一行包含一个整数 $t$ $(1 \leq t \leq 10000)$，表示输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 300000)$，分别表示数组 $a$ 的长度和数字 $x_i$ 的数量。

第二行包含 $m$ 个整数 $x_1, x_2, \ldots, x_m$ $(-10^{9} \leq x_i \leq 10^{9})$，描述这些数字的值。

设 $N$ 为所有数据组中 $n$ 的总和，$M$ 为所有数据组中 $m$ 的总和。保证 $N$ 和 $M$ 均不超过 $300000$。

输出格式

对于每组输入数据，在单独的一行中输出一个数字，即通过最优操作可获得的数组 $a$ 的最大元素之和。

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$。可以证明，无法获得更大的和。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。