题目描述

洛天依给了你一个包含 $n \cdot m$ 个整数的数组 $b$。她要求你构造一个大小为 $n \times m$ 的表格 $a$，用这 $n \cdot m$ 个数填满，每个数必须且只能用一次。同时，她还要求你最大化如下的值：

也就是说，我们考虑 $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$。

输出格式

对于每个测试用例，输出一个整数，表示可以获得的最大值。

说明/提示

在第一个测试用例中，表格如下：

4 1
1 3

对于以 $(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$。

由 ChatGPT 4.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

9
0
64
71
1933711