Un mapa es una grilla de \(R \times C\) celdas con alturas. Vas de la celda de arriba a la izquierda a la de abajo a la derecha moviéndote arriba, abajo, izquierda o derecha. El esfuerzo de un recorrido es la mayor diferencia absoluta de altura entre dos celdas consecutivas del recorrido. Encuentra el menor esfuerzo posible.

Entrada

La primera línea tiene \(R\) y \(C\) \((1 \le R \cdot C \le 9 \cdot 10^4)\). Siguen \(R\) líneas con \(C\) alturas cada una, entre \(1\) y \(10^6\).

Salida

El menor esfuerzo.

Ejemplo 1

Entrada

3 3
1 2 2
3 8 2
5 3 5

Salida

2

Ejemplo 2

Entrada

3 3
1 2 3
3 8 4
5 3 5

Salida

1

Ejemplo 3

Entrada

1 1
7

Salida

0