El trayecto de esquí a campo traviesa en las Mulimpiadas de invierno está descrito como una cuadrícula de alturas ~M~ x ~N~ ~(1 \leq M, N \leq 500)~, cada elevación en el rango ~0... 1 000 000 000~.

Algunas de las celdas en esta cuadrícula están designadas como puntos de camino para el trayecto. Los organizadores de las Mulimpiadas quieren asignar un rango de dificultad ~D~ a todo el trayecto de tal manera que una vaca pueda llegar de cualquier punto de camino a otro punto de camino esquiando repetidamente de una celda a una celda adyacente entre celdas adyacentes con diferencia absoluta de altura de a lo más ~D~. Dos celdas son adyacentes si una está directamente al norte, sur, este u oeste de la otra. El rango de dificultad del trayecto es el ~D~ mínimo tal que todos los puntos del camino son alcanzables mutuamente de esta manera.

Entrada

• Línea 1: Los enteros ~M~ y ~N~.

• Líneas 2…1+M: Cada una de esas ~M~ líneas contiene ~N~ alturas enteras.

• Líneas 2+M…1+2M: Cada una de esas líneas contiene ~N~ valores que son o ~0~ o ~1~, con ~1~ indicando que ~1~ es un punto de camino.

Ejemplo de Entrada

3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

Detalles de la Entrada

El trayecto de esquí está descrito por una cuadrícula de alturas ~3~ x ~5~. Las celdas superior-izquierda, superior-derecha e inferior-derecha están designadas como puntos de camino.

Salida

• Línea 1: El rango de dificultad para el trayecto (el valor mínimo de ~D~ tal que todos los puntos de camino estén aún conectados desde cada otro).

Ejemplo de Salida

21

Detalles de la Salida

Si ~D = 21~, todos los tres puntos de camino son alcanzables desde cada otro. Si ~D < 21~, entonces el punto de camino superior-derecho no puede ser alcanzable desde los otros dos.