Alice i Bob grają w grę na siatce o $N$ wierszach i $M$ kolumnach, gdzie $M$ jest liczbą parzystą. Dana jest również dodatnia liczba całkowita $K$. Początkowo każda komórka siatki zawiera wartość z przedziału od $0$ do $K$ włącznie, a każda komórka jest nieoznaczona. Gracze wykonują ruchy na zmianę, przy czym Alice zaczyna jako pierwsza. Gra kończy się, gdy bieżący gracz nie może wykonać ruchu.
W swojej turze gracz wybiera nieoznaczoną komórkę siatki oraz liczbę całkowitą $a$ z przedziału od $0$ do $K$ włącznie. Następnie ustawia wartość tej komórki na $a$ i oznacza wszystkie komórki w tej samej kolumnie, w której znajduje się wybrana komórka (wliczając w to wybraną komórkę).
Asymetria siatki to suma wartości bezwzględnych różnic między wartością komórki a wartością jej odpowiednika przy odbiciu poziomym względem środka siatki, obliczona dla wszystkich takich par komórek. Formalnie jest to:
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
gdzie $g_{i,j}$ jest wartością komórki w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej. Na przykład, poniższa siatka $2 \times 4$ ma asymetrię równą $|8-0| + |4-2| + |6-6| + |7-9| = 12$.
| 8 | 4 | 2 | 0 |
|---|---|---|---|
| 6 | 7 | 9 | 6 |
Alice chce zminimalizować asymetrię siatki po zakończeniu gry, podczas gdy Bob chce ją zmaksymalizować. Jeśli obaj gracze grają optymalnie, jaka będzie asymetria końcowej siatki?
Wejście
Pierwsza linia wejścia zawiera trzy liczby całkowite oddzielone spacjami $N$, $M$ oraz $K$ ($1 \le N, M \le 2000$, $M$ jest parzyste, $1 \le K \le 10^9$).
Kolejne $N$ linii zawiera po $M$ liczb całkowitych, gdzie $i$-ta linia zawiera liczby $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$), będące wartościami komórek od lewej do prawej w $i$-tym wierszu od góry.
Poniższa tabela przedstawia podział 25 dostępnych punktów:
| Przyznane punkty | Ograniczenia na $N$ | Ograniczenia na $M$ | Ograniczenia na $K$ |
|---|---|---|---|
| 2 punkty | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3 punkty | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3 punkty | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3 punkty | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4 punkty | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4 punkty | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6 punktów | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
Wyjście
Wypisz pojedynczą liczbę całkowitą: asymetrię końcowej siatki, jeśli Alice i Bob grają optymalnie.
Przykład
Wejście 1
3 2 1 1 0 1 0 0 0
Wyjście 1
2
Uwagi 1
Istnieją tylko 2 kolumny, więc każdy gracz wykona 1 ruch. Zaczynając jako pierwsza, Alice może wykonać następujące ruchy:
- Wybrać jedną z komórek o wartości 1 w pierwszej kolumnie i ustawić jej wartość na 0. Wtedy optymalnym ruchem dla Boba jest ustawienie wartości komórki w tym samym wierszu w drugiej kolumnie na 1. Końcowa siatka będzie wyglądać jak oryginalna z dokładnie jednym zamienionym wierszem spośród pierwszych dwóch wierszy zer i jedynek. Taka siatka ma asymetrię $|1-0| + |0-1| + |0-0| = 2$.
- Wybrać jedną z komórek w drugiej kolumnie i pierwszych dwóch wierszach i ustawić jej wartość na 1. Wtedy optymalnym ruchem dla Boba jest ustawienie wartości komórki w tym samym wierszu w pierwszej kolumnie na 0. Ponownie, końcowa siatka będzie wyglądać jak oryginalna z dokładnie jednym zamienionym wierszem spośród pierwszych dwóch wierszy zer i jedynek. Taka siatka ma asymetrię 2.
- Wybrać jedną z komórek w trzecim wierszu i ustawić jej wartość na 1. Wtedy optymalnym ruchem dla Boba może być ustawienie wartości drugiej komórki w trzecim wierszu na 0. Zauważ, że wybrana komórka miała już wartość 0 i taki ruch jest dozwolony. Wtedy końcowa siatka będzie miała 0 i 1 w każdym wierszu, co skutkuje asymetrią 3.
- Wybrać dowolną komórkę i ustawić jej wartość na obecną. Wtedy optymalnym ruchem dla Boba jest ustawienie wartości komórki w pozostałej nieoznaczonej kolumnie i trzecim wierszu na 1. Końcowa siatka będzie miała 0 i 1 w każdym wierszu, co skutkuje asymetrią 3.
Widzimy, że niezależnie od tego, jak Alice wykona swój ruch, Bob będzie w stanie zagrać w taki sposób, że asymetria wyniesie co najmniej 2. Jeśli Alice wybierze swój pierwszy ruch optymalnie, może zapewnić, że Bob nie sprawi, iż końcowa asymetria przekroczy 2. Zatem asymetria przy optymalnej grze obu graczy wynosi 2.
Wejście 2
1 10 21 4 2 0 6 7 6 9 9 10 21
Wyjście 2
55
Uwagi 2
Jest tylko jeden wiersz, więc w każdym ruchu bieżący gracz wybierze nieoznaczoną komórkę i ustawi ją na dowolną wartość z przedziału od 0 do 21 włącznie. Gra kończy się po wykonaniu przez każdego gracza 5 ruchów, co skutkuje oznaczeniem wszystkich 10 komórek.
Wejście 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
Wyjście 3
3972378656
Uwagi 3
Zauważ, że odpowiedź może nie mieścić się w 32-bitowej liczbie całkowitej.