CF1825B.LuoTianyi and the Table

LuoTianyi gave an array $b$ of $n \cdot m$ integers. She asks you to construct a table $a$ of size $n \times m$, filled with these $n \cdot m$ numbers, and each element of the array must be used exactly once. Also she asked you to maximize the following value:

$\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}\right)$

This means that we consider $n \cdot m$ subtables with the upper left corner in $(1,1)$ and the bottom right corner in $(i, j)$ ($1 \le i \le n$, $1 \le j \le m$), for each such subtable calculate the difference of the maximum and minimum elements in it, then sum up all these differences. You should maximize the resulting sum.

Help her find the maximal possible value, you don't need to reconstruct the table itself.

洛天依给出一个包含 $n \cdot m$ 个整数的数组 $b$。她要求你用这 $n \cdot m$ 个数构造一个大小为 $n \times m$ 的表格 $a$，其中每个数恰好使用一次。此外，她还要求最大化以下值：

$$\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}\right)$$

这意味着：我们考虑所有以 $(1,1)$ 为左上角、$(i, j)$ 为右下角的子表格（其中 $1 \le i \le n$，$1 \le j \le m$），共 $n \cdot m$ 个；对每个这样的子表格，计算其内部最大值与最小值之差；最后将所有这些差值求和。你需要使该总和尽可能大。

请帮她找出可能的最大值，你无需实际构造出对应的表格。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 100$) — the number of rows and columns of the table.

The second line of each test case contains $n \cdot m$ integers $b_1, b_2, \ldots, b_{n\cdot m}$ ($-10^5 \le b_{i} \le 10^5$) — the numbers you can put in the table.

Note, that integers in the array $b$ can be negative.

It is guaranteed that the sum of $n \cdot m$ over all test cases doesn't exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the maximal value, that can be obtained.

对于每个测试用例，输出一个整数——所能获得的最大值。

In the first test case, the table is follows:

4

1

1

3

In the subtable with the bottom right corner in $(1, 1)$, the difference of the maximal and minimal elements is $4 - 4 = 0$.

In the subtable with the bottom right corner in $(1, 2)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.

In the subtable with the bottom right corner in $(2, 1)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.

In the subtable with the bottom right corner in $(2, 2)$, the difference of the maximal and minimal elements is $4 - 1 = 3$.

Then the maximum possible value is $0+3+3+3=9$.

In the second test case, all elements are equal, so all differences are $0$, and the answer is $0$.

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

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$。