Alice y Bob jugarán un juego con una cuadrícula de $N$ filas y $M$ columnas, donde $M$ es par. También hay un entero positivo $K$. Inicialmente, cada celda de la cuadrícula contiene un valor entre $0$ y $K$, inclusive, y cada celda está sin marcar. Los jugadores toman turnos alternativamente, comenzando Alice. El juego termina cuando el jugador en turno no puede realizar un movimiento.
En el turno de cada jugador, seleccionan una celda sin marcar de la cuadrícula y un entero $a$ entre $0$ y $K$, inclusive. Luego, establecen el valor de esa celda en $a$ y marcan todas las celdas en la misma columna que la seleccionada (incluyendo la celda seleccionada).
La asimetría de la cuadrícula es la suma de las diferencias absolutas entre el valor de una celda y su celda correspondiente cuando se refleja horizontalmente a través del centro de la cuadrícula sobre todos esos pares de celdas. Más formalmente, es:
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
donde $g_{i,j}$ es el valor de la celda en la $i$-ésima fila desde arriba y la $j$-ésima columna desde la izquierda. Por ejemplo, la siguiente cuadrícula de $2 \times 4$ tiene una asimetría de $|8-0| + |4-2| + |6-6| + |7-9| = 12$.
Alice desea minimizar la asimetría de la cuadrícula cuando el juego termina, mientras que Bob desea maximizarla. Si ambos jugadores juegan de manera óptima, ¿cuál es la asimetría de la cuadrícula final?
Entrada
La primera línea de la entrada consistirá en tres enteros separados por espacios $N$, $M$ y $K$ ($1 \le N, M \le 2000$, $M$ es par, $1 \le K \le 10^9$).
Las siguientes $N$ líneas contienen cada una $M$ enteros, donde la $i$-ésima línea contiene los enteros $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$), los valores de las celdas de izquierda a derecha en la $i$-ésima fila desde arriba.
Salida
Imprima un solo entero, la asimetría de la cuadrícula final si Alice y Bob juegan de manera óptima.
Subtareas
| Puntos | Restricciones en $N$ | Restricciones en $M$ | Restricciones en $K$ |
|---|---|---|---|
| 2 puntos | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3 puntos | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3 puntos | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3 puntos | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4 puntos | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4 puntos | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6 puntos | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
Ejemplos
Entrada 1
3 2 1 1 0 1 0 0 0
Salida 1
2
Nota 1
Solo hay 2 columnas, por lo que cada jugador realizará 1 movimiento. Con Alice comenzando, ella puede realizar los siguientes movimientos:
- Seleccionar una de las celdas con un valor de 1 en la primera columna y establecer su valor a 0. Entonces, el movimiento óptimo para Bob es establecer el valor de la celda en la misma fila en la segunda columna a 1. La cuadrícula final será como la original con exactamente una de las dos primeras filas de 0s y 1s intercambiadas. Tal cuadrícula tiene una asimetría de $|1-0| + |0-1| + |0-0| = 2$.
- Seleccionar una de las celdas en la segunda columna y las dos primeras filas y establecer su valor a 1. Entonces, el movimiento óptimo para Bob es establecer el valor de la celda en la misma fila en la primera columna a 0. Nuevamente, la cuadrícula final será como la original con exactamente una de las dos primeras filas de 0s y 1s intercambiadas. Tal cuadrícula tiene una asimetría de 2.
- Seleccionar una de las celdas en la tercera fila y establecer su valor a 1. Entonces, el movimiento óptimo para Bob puede ser establecer el valor de la otra celda en la tercera fila a 0. Note que la celda seleccionada ya tenía el valor de 0, y que tal movimiento está permitido. Entonces, la cuadrícula final tendrá un 0 y un 1 en cada fila, resultando en una asimetría de 3.
- Seleccionar cualquier celda y establecer su valor a su valor actual. Entonces, el movimiento óptimo para Bob es establecer el valor de la celda en la columna restante sin marcar y la tercera fila a 1. La cuadrícula final tendrá un 0 y un 1 en cada fila, resultando en una asimetría de 3.
Vemos que independientemente de cómo Alice haga su movimiento, Bob podrá jugar de tal manera que la asimetría sea al menos 2. Si Alice selecciona su primer movimiento de manera óptima, puede asegurar que Bob no pueda hacer que la asimetría final sea mayor a 2. Por lo tanto, la asimetría si ambos jugadores juegan de manera óptima es 2.
Entrada 2
1 10 21 4 2 0 6 7 6 9 9 10 21
Salida 2
55
Nota 2
Solo hay una fila, por lo que para cada movimiento, el jugador actual seleccionará una celda sin marcar y la establecerá a cualquier valor entre 0 y 21, inclusive. El juego termina después de que cada jugador haya realizado 5 movimientos, resultando en que todas las 10 celdas estén marcadas.
Entrada 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
Salida 3
3972378656
Nota 3
Note que la respuesta puede no caber en un entero de 32 bits.