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\)), вычисляем для каждой такой подтаблицы разность максимального и минимального элементов в ней, после чего суммируем все эти разности. Вы должны максимизировать получившуюся сумму.
Помогите ей найти максимально возможное такое значение, саму таблицу вам при этом восстанавливать не нужно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение, которое можно получить.
Примечание
В первом наборе входных данных таблица выглядит так:
В подтаблице с правым нижним углом в \((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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|