Description

Oleg 和 Dasha 参加了一场团队竞赛，但遗憾的是他们没有解决任何问题。Oleg 很快意识到他们的团队训练不足，于是他们的共同朋友给他们推荐了一道有趣的练习题。这道题非常简单，只需要掌握整数的加法和减法就可以完成。

给定一个长度为 $n$ 的数组，初始时数组内所有元素均为0。现在你有 $m$ 个数 $x_1, x_2, \dots, x_m$。对于从 $1$ 到 $m$ 的每个 $i$，你需要选择一个位置 $j_i$，并执行操作：

$$a_{j_i} = x_i - a_{j_i}$$

请你帮助 Oleg 和 Dasha 确定，在你做出最佳选择的情况下，最终数组所有元素的总和最大能达到多少。

Format

Input

输入包含多组测试数据。

第一行包含一个整数 $t$（$1 \leq t \leq 10000$），表示测试数据的组数。以下依次是每组测试数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300000$），分别表示数组长度和数值数量。

每组数据的第二行包含 $m$ 个整数 $x_1, x_2, \dots, x_m$（$-10^9 \leq x_i \leq 10^9$），表示进行操作的数值。

设 $N$ 是所有数据集中 $n$ 的总和，$M$ 是所有数据集中 $m$ 的总和。

保证 $N \leq 300000$、$M \leq 300000$。

Output

对于每组测试数据，输出一行一个整数，表示能获得的数组总和的最大值。

Samples

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

Note

对于第一组数据，所有操作依次作用于数组第一个元素，数组变化过程为：

• 初始：[0]
• 第一步：$1-0=1$，数组变为[1]
• 第二步：$2-1=1$，数组变为[1]
• 第三步：$3-1=2$，数组变为[2]
• 第四步：$4-2=2$，数组变为[2]

因此，最终和为2。

对于第二组数据，一种最优策略为：

• $a_1=10-0=10$，数组变为[10,0]
• $a_1=3-10=-7$，数组变为[-7,0]
• $a_1=7-(-7)=14$，数组变为[14,0]
• $a_1=1-14=-13$，数组变为[-13,0]
• $a_2=4-0=4$，数组变为[-13,4]
• $a_1=6-(-13)=19$，数组变为[19,4]
• $a_2=3-4=-1$，数组变为[19,-1]

最终数组为[19,-1]，总和为18。

Limitation

时间限制：1s
空间限制：1024KiB

Scoring

本题分为10个子任务，每个子任务的得分情况如下，只有通过本组所有数据以及所有必需的前置组数据才能得到对应分数。

组别	分值	附加条件	必需通过组	备注
0		-	-	样例
1	4	$0 \leq x_i$，所有 $x_i$ 相同		-
2	8	$n=2$, $M \leq 30$, $m \leq 18$
3	11	$n=2$, $M \leq 50$, $-10 \leq x_i \leq 10$
4	9	$n=2$, $M \leq 400$, $-400 \leq x_i \leq 400$	3
5	8	$N \leq 30$, $M \leq 30$, $m \leq 18$	0
6	10	$N \leq 2000$, $M \leq 2000$, $0 \leq x_i$	-
7	12	$N \leq 2000$, $M \leq 2000$	0,2-6
8	10	$0 \leq x_i$	1	$x_i$ 最多只有两种不同的值
9	17		1,6,8	-
10	11	-	0-9	离线评测