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

У Алисы и Боба есть $$$k$$$ массивов длины $$$n$$$. Они играют в следующую игру. Алиса выбирает любой массив, длина которого больше 1, делит его на два массива ненулевой длины и заменяет выбранный массив на два получившихся. Более формально, Алиса выбирает массив $$$[a_{1}, a_{2}, \ldots, a_{s}]$$$ и индекс $$$j$$$ ($$$1 \leq j \lt s$$$) и заменяет массив $$$[a_{1}, a_{2}, \ldots, a_{s}]$$$ на $$$[a_{1}, a_{2}, \ldots, a_{j}]$$$ и $$$[a_{j + 1}, \ldots, a_{s}]$$$. После этого Боб выбирает любой массив из существующих и удаляет его. Игра заканчивается, когда игрок не может сделать очередной ход. В конце игры останутся только массивы размера $$$1$$$, а итоговый счёт игры равен сумме оставшихся элементов. Алиса хочет минимизировать счёт игры, а Боб наоборот хочет максимизировать. Найдите счёт этой игры, если Алиса и Боб играют оптимально.

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

Первая строка содержит два целых числа $$$k$$$ и $$$n$$$ ($$$1 \leq k, n \leq 200\,000$$$, $$$k \cdot n \leq 200\,000$$$) — количество массивов и длину каждого массива.

Следующие $$$k$$$ строк содержат $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \leq a_{i,j} \leq 10^{9}$$$) — описание очередного массива.

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

В единственной строке выведите счёт игры, если Алиса и Боб играют оптимально.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в C и C++, тип long в Java и C#, тип int64 в языке Pascal). Язык Python будет корректно работать и с типом int.

Система оценки

В данной задаче 25 тестов, каждый из которых оценивается в 4 балла.

Гарантируется, что решения корректно работающие при $$$1 \leq k \cdot n \leq 12$$$, наберут не менее $$$20$$$ баллов.

Гарантируется, что решения корректно работающие при $$$1 \leq k \leq 10$$$, наберут не менее $$$40$$$ баллов.

Гарантируется, что решения корректно работающие при $$$1 \leq n \leq 10$$$, наберут не менее $$$32$$$ баллов.

Обратите внимание, тесты могут удовлетворять сразу нескольким ограничениям выше.

Примеры
Входные данные
2 2
1 2
2 3
Выходные данные
5
Входные данные
3 4
8 5 6 6
6 2 2 9
7 6 8 9
Выходные данные
26
Примечание

В первом наборе входных данных Боб может гарантировать счёт $$$5$$$ вне зависимости от ходов Алисы. Если Алиса разделит массив $$$[1, 2]$$$ на $$$[1]$$$ и $$$[2]$$$, то Боб удалит массив $$$[1]$$$, после этого у Алисы будет единственный ход разделить $$$[2, 3]$$$ на $$$[2]$$$ и $$$[3]$$$, тогда Боб удалит любой из массивов $$$[2]$$$, и игра закончится. Если же Алиса своим первым ходом разделит массив $$$[2, 3]$$$, то Боб удалит массив $$$[1, 2]$$$, и игра также закончится со счётом $$$5$$$.