У Алисы и Боба есть $$$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 21 22 3
5
3 48 5 6 66 2 2 97 6 8 9
26
В первом наборе входных данных Боб может гарантировать счёт $$$5$$$ вне зависимости от ходов Алисы. Если Алиса разделит массив $$$[1, 2]$$$ на $$$[1]$$$ и $$$[2]$$$, то Боб удалит массив $$$[1]$$$, после этого у Алисы будет единственный ход разделить $$$[2, 3]$$$ на $$$[2]$$$ и $$$[3]$$$, тогда Боб удалит любой из массивов $$$[2]$$$, и игра закончится. Если же Алиса своим первым ходом разделит массив $$$[2, 3]$$$, то Боб удалит массив $$$[1, 2]$$$, и игра также закончится со счётом $$$5$$$.
