310382: CF1825B. LuoTianyi and the Table

B. LuoTianyi and the Tabletime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

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

Output

9
0
64
71
1933711

Note

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

洛天依给了你一个含有 $ n \times m $ 个整数的数组 $ b $。她要求你构建一个 $ 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) 为右下角的 $ n \times m $ 个子表格，对于每个这样的子表格，计算其中的最大元素和最小元素的差，然后将所有这些差加起来。你应该最大化这个结果的总和。

输入数据格式：
- 每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 200 $）——测试用例的数量。
- 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 2 \le n, m \le 100 $）——表格的行数和列数。
- 每个测试用例的第二行包含 $ n \times m $ 个整数 $ b_1, b_2, \ldots, b_{n\cdot m} $（$ -10^5 \le b_{i} \le 10^5 $）——你可以放入表格中的数字。
- 数组 $ b $ 中的整数可以是负数。
- 保证所有测试用例的 $ n \times m $ 之和不超过 $ 2 \times 10^5 $。

输出数据格式：
- 对于每个测试用例，输出一个整数——可以获得的最大值。

示例输入输出：
```
Input
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

Output
9
0
64
71
1933711
```

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

```
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。洛天依给了你一个含有 $ n \times m $ 个整数的数组 $ b $。她要求你构建一个 $ 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) 为右下角的 $ n \times m $ 个子表格，对于每个这样的子表格，计算其中的最大元素和最小元素的差，然后将所有这些差加起来。你应该最大化这个结果的总和。 输入数据格式： - 每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 200 $）——测试用例的数量。 - 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 2 \le n, m \le 100 $）——表格的行数和列数。 - 每个测试用例的第二行包含 $ n \times m $ 个整数 $ b_1, b_2, \ldots, b_{n\cdot m} $（$ -10^5 \le b_{i} \le 10^5 $）——你可以放入表格中的数字。 - 数组 $ b $ 中的整数可以是负数。 - 保证所有测试用例的 $ n \times m $ 之和不超过 $ 2 \times 10^5 $。 输出数据格式： - 对于每个测试用例，输出一个整数——可以获得的最大值。 示例输入输出： ``` Input 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 Output 9 0 64 71 1933711 ``` 注意：在第一个测试用例中，表格如下： ``` 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。