Алиса и Боб играют в игру на сетке из $N$ строк и $M$ столбцов, где $M$ — чётное число. Также дано положительное целое число $K$. Изначально каждая ячейка сетки содержит значение от $0$ до $K$ включительно, и каждая ячейка является невыделенной. Игроки ходят по очереди, Алиса ходит первой. Игра заканчивается, когда текущий игрок не может сделать ход.
В свой ход игрок выбирает невыделенную ячейку сетки и целое число $a$ от $0$ до $K$ включительно. Затем он устанавливает значение этой ячейки равным $a$ и помечает все ячейки в том же столбце, что и выбранная (включая саму выбранную ячейку).
Асимметрия сетки — это сумма абсолютных разностей между значением ячейки и значением соответствующей ей ячейки при горизонтальном отражении относительно середины сетки по всем таким парам ячеек. Формально, это:
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
где $g_{i,j}$ — значение ячейки в $i$-й строке сверху и $j$-м столбце слева. Например, следующая сетка $2 \times 4$ имеет асимметрию $|8-0| + |4-2| + |6-6| + |7-9| = 12$.
Алиса хочет минимизировать асимметрию сетки к моменту окончания игры, а Боб хочет её максимизировать. Если оба игрока играют оптимально, чему будет равна асимметрия итоговой сетки?
Входные данные
Первая строка входных данных содержит три целых числа $N$, $M$ и $K$ ($1 \le N, M \le 2000$, $M$ — чётное, $1 \le K \le 10^9$).
Следующие $N$ строк содержат по $M$ целых чисел, где $i$-я строка содержит числа $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$), значения ячеек слева направо в $i$-й строке сверху.
Подзадачи
| Награда | Ограничения на $N$ | Ограничения на $M$ | Ограничения на $K$ |
|---|---|---|---|
| 2 балла | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3 балла | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3 балла | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3 балла | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4 балла | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4 балла | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6 баллов | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
Выходные данные
Выведите единственное целое число — асимметрию итоговой сетки, если Алиса и Боб играют оптимально.
Примеры
Примеры 1
3 2 1 1 0 1 0 0 0
2
Примечание к примеру 1
Всего 2 столбца, поэтому каждый игрок сделает по 1 ходу. Алиса ходит первой, она может сделать следующие ходы:
- Выбрать одну из ячеек со значением 1 в первом столбце и установить её значение равным 0. Тогда оптимальный ход Боба — установить значение ячейки в той же строке во втором столбце равным 1. Итоговая сетка будет похожа на исходную, но в одной из первых двух строк значения 0 и 1 поменяются местами. Такая сетка имеет асимметрию $|1-0| + |0-1| + |0-0| = 2$.
- Выбрать одну из ячеек во втором столбце в первых двух строках и установить её значение равным 1. Тогда оптимальный ход Боба — установить значение ячейки в той же строке в первом столбце равным 0. Снова итоговая сетка будет похожа на исходную, но в одной из первых двух строк значения 0 и 1 поменяются местами. Такая сетка имеет асимметрию 2.
- Выбрать одну из ячеек в третьей строке и установить её значение равным 1. Тогда оптимальный ход Боба может заключаться в том, чтобы установить значение другой ячейки в третьей строке равным 0. Заметим, что выбранная ячейка уже имела значение 0, и такой ход разрешён. Тогда в итоговой сетке будет 0 и 1 в каждой строке, что приведёт к асимметрии 3.
- Выбрать любую ячейку и установить её значение равным текущему. Тогда оптимальный ход Боба — установить значение ячейки в оставшемся невыделенном столбце и третьей строке равным 1. В итоговой сетке будет 0 и 1 в каждой строке, что приведёт к асимметрии 3.
Мы видим, что независимо от того, как Алиса делает свой ход, Боб сможет сыграть так, чтобы асимметрия была не менее 2. Если Алиса выберет свой первый ход оптимально, она может гарантировать, что Боб не сможет сделать итоговую асимметрию больше 2. Таким образом, асимметрия при оптимальной игре обоих игроков равна 2.
Примеры 2
1 10 21 4 2 0 6 7 6 9 9 10 21
55
Примечание к примеру 2
Есть только одна строка, поэтому для каждого хода текущий игрок выбирает невыделенную ячейку и устанавливает её значение равным любому числу от 0 до 21 включительно. Игра заканчивается после того, как каждый игрок сделал по 5 ходов, в результате чего все 10 ячеек оказываются помеченными.
Примеры 3
4 6 986754321 219759391 882760615 762656191 423465948 621463211 136889371 215621504 385106915 740086459 417915224 551800597 572994766 176308756 365311996 635683450 907755406 590000050 586083433 607011121 457147795 837558908 684766852 946836347 303039615
3972378656
Примечание к примеру 3
Заметьте, что ответ может не поместиться в 32-битное целое число.