D. Скибидус и сигма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обозначим оценку массива $$$b$$$ с $$$k$$$ элементами как $$$\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)$$$. Иными словами, пусть $$$S_i$$$ обозначает сумму первых $$$i$$$ элементов массива $$$b$$$. Тогда оценка может быть записана как $$$S_1+S_2+\ldots+S_k$$$.

Скибидусу даны $$$n$$$ массивов $$$a_1,a_2,\ldots,a_n$$$, каждый из которых содержит $$$m$$$ элементов. Будучи тем самым сигмой, он хотел бы объединить их в любом порядке, чтобы получить один массив, содержащий $$$n\cdot m$$$ элементов. Пожалуйста, найдите максимальную возможную оценку, которую Скибидус может достичь с помощью своего объединенного массива!

Формально, среди всех возможных перестановок$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$, выведите максимальную оценку для $$$a_{p_1} + a_{p_2} + \dots + a_{p_n}$$$, где $$$+$$$ обозначает объединение$$$^{\text{†}}$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ содержит все целые числа от $$$1$$$ до $$$n$$$ ровно один раз.

$$$^{\text{†}}$$$Объединение двух массивов $$$c$$$ и $$$d$$$ с длинами $$$e$$$ и $$$f$$$ соответственно (т.е. $$$c + d$$$) это $$$c_1, c_2, \ldots, c_e, d_1, d_2, \ldots d_f$$$.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — количество массивов и длину каждого массива.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 10^6$$$) — элементы $$$i$$$-го массива.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите максимальную оценку среди всех возможных перестановок $$$p$$$ на новой строке.

Пример
Входные данные
3
2 2
4 4
6 1
3 4
2 2 2 2
3 2 1 2
4 1 2 1
2 3
3 4 5
1 1 9
Выходные данные
41
162
72
Примечание

Для первого набора входных данных есть две возможности для $$$p$$$:

  • $$$p = [1, 2]$$$. Тогда $$$a_{p_1} + a_{p_2} = [4, 4, 6, 1]$$$. Его оценка равна $$$4+(4+4)+(4+4+6)+(4+4+6+1)=41$$$.
  • $$$p = [2, 1]$$$. Тогда $$$a_{p_1} + a_{p_2} = [6, 1, 4, 4]$$$. Его оценка равна $$$6+(6+1)+(6+1+4)+(6+1+4+4)=39$$$.

Максимально возможная оценка равна $$$41$$$.

Во втором наборе входных данных одна из оптимальных расстановок окончательного объединенного массива: $$$[4,1,2,1,2,2,2,2,3,2,1,2]$$$. Мы можем вычислить, что оценка равна $$$162$$$.