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

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

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