题目描述

题目译自 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$ 的元素之和的最大值。

输入格式

每个测试点包含多组输入数据。

1. 第一行：整数 $t$（$1 \leq t \leq 10000$），表示输入数据的组数；
2. 每组数据：
   • 第一行：两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300000$），分别表示数组长度和数字数量；
   • 第二行：$m$ 个整数 $x_1, x_2, \ldots, x_m$（$-10^9 \leq x_i \leq 10^9$）。

所有数据组中 $n$ 的总和 $N$ 和 $m$ 的总和 $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