Codeforces Round 872 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

math

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. LuoTianyi and the Table

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLuoTianyi 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:

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.

Example

Input

52 21 3 1 42 2-1 -1 -1 -12 37 8 9 -3 10 83 24 8 -3 0 -7 14 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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:21:05 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|