B. LuoTianyi и таблица
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

LuoTianyi дала массив $$$b$$$ из $$$n \cdot m$$$ целых чисел. Она просит вас построить таблицу $$$a$$$ размера $$$n \times m$$$, заполненную этими $$$n \cdot m$$$ числами, при этом каждый элемент массива должен быть использован ровно один раз. Также она попросила, чтобы следующее значение было максимально:

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

Это означает, что мы рассматриваем $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное значение, которое можно получить.

Пример
Входные данные
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
Примечание

В первом наборе входных данных таблица выглядит так:

41
13

В подтаблице с правым нижним углом в $$$(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$$$.