LuoTianyi 给出了一个 $$$b$$$ 个 $$$n \cdot m$$$ 个整数的数组。她要求你构造一个大小为 $$$n \times m$$$ 的表 $$$a$$$,用这些 $$$n \cdot m$$$ 数字填充,并且数组的每个元素必须恰好使用一次。她还要求你最大化以下值:
$$$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\右)$$$
这意味着我们考虑 $$$n \cdot m$$$ 子表,其左上角在 $$$(1,1)$$$ 中,右下角在 $$$(i, j)$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$),对于每个这样的子表,计算其中最大和最小元素的差,然后将所有这些求和差异。您应该最大化所得总和。
帮助她找到最大可能值,您不需要重建表格本身。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 100$$$) — 表的行数和列数。
每个测试用例的第二行包含 $$$n \cdot m$$$ 整数 $$$b_1, b_2, \ldots, b_{n\cdot m}$$$ ($$$-10^5 \le b_{i} \le 10^5$$$) — 您可以放入表中的数字。
请注意,数组 $$$b$$$ 中的整数可以为负数。
保证所有测试用例的 $$$n \cdot m$$$ 之和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 可以获得的最大值。
示例
输入 #1
5 2 2 1 3 1 4 2 2 -1 -1 -1 -1 2 3 7 8 9 -3 10 8 3 2 4 8 -3 0 -7 1 4 3 -32030 59554 16854 -85927 68060 -64460 -79547 90932 85063 82703 -12001 38762
输出 #1
9 0 64 71 1933711
注意
第一个测试用例中,表格如下:
4113
在$$$(1, 1)$$$右下角的子表中,最大元素和最小元素之差为$$$4 - 4 = 0$$$。
在$$$(1, 2)$$$右下角的子表中,最大元素和最小元素之差为$$$4 - 1 = 3$$$。
在$$$(2, 1)$$$右下角的子表中,最大元素和最小元素之差为$$$4 - 1 = 3$$$。
在$$$(2, 2)$$$右下角的子表中,最大元素和最小元素之差为$$$4 - 1 = 3$$$。
那么最大可能值为$$$0+3+3+3=9$$$。
在第二个测试用例中,所有元素都相等,因此所有差异都是 $$$0$$$,答案是 $$$0$$$。