Los antiguos jueces Ent de la UMSA tenían varias tradiciones al organizar concursos: incluir un problema que se resolviera usando $N(N + 1)/2$, mencionar al Botas en algún enunciado, lograr que Chuck Norris ganara el contest, olvidarse de probar algún caso, ir a comer una mega burger al terminar, o sufrir algún evento desafortunado que mantuviera a todos preocupados durante toda la competencia.

Cuenta la leyenda que llegó el día en que a nuestro querido competidor Botas le tocó organizar su primera DIV 2. Entre recibir problemas, escribir casos de prueba, revisar soluciones y comprar los globos para el concurso, apenas tenía tiempo para respirar.

Desesperado, fue al legendario laboratorio Patito a preguntarle a Addis cuántos globos debía comprar.

Addis, que por aquella época no estaba precisamente cuerdo, respondió:

• Tengo una lista de los participantes.
• Los sentaremos en una cuadrícula de $N$ filas y $M$ columnas dentro del laboratorio.
• A cada participante le he asignado un número $B_{i,j}$ que representa qué tan bueno es compitiendo.
• Frente a cada participante colocaremos una cuerda con globos.
• Cada participante debe tener al menos un globo.
• Si un participante es mejor que otro participante sentado en una posición adyacente, entonces su cuerda debe verse más impresionante.
• Dos posiciones son adyacentes si comparten un lado (arriba, abajo, izquierda o derecha).
• Una cuerda se considera más impresionante si tiene estrictamente más globos.
• Deberías comprar la menor cantidad posible de globos para poder cumplir estas condiciones.

Botas estaba seguro de que Addis estaba bromeando o simplemente había perdido la cordura, pero prefirió hacerle caso.

Ayuda a Botas a determinar cuántos globos debe comprar.

La primera línea contiene dos enteros $N$ y $M$ ($1 \le N \cdot M \le 10^6$), que representan el número de filas y columnas de participantes.

Las siguientes $N$ líneas contienen $M$ enteros cada una. El entero $B_{i,j}$ ($0 \le B_{i,j} \le 10^5$) representa qué tan bueno es el participante sentado en la fila $i$ y columna $j$.

Imprime un único entero: la cantidad mínima de globos que Botas debe comprar.

Puedes darle 2 globos al primer participante, 1 globo al segundo y 2 globos al tercero.

Puedes darle 1 globo al primer participante, 2 globos al segundo y 1 globo al tercero. Nota que el segundo participante es mejor que el primero, por lo que debe tener más globos.

Una distribución válida es:

1 2
2 3

Cada participante tiene al menos un globo, y cualquier participante con un valor mayor que el de un vecino adyacente recibe más globos que dicho vecino. No existe una distribución válida con menos de 8 globos.