Los monos han iniciado una invasión. Planean apoderarse del mundo. Después de secuestrar una flota de planeadores de la Ciudad de los Gnomos (¡los gnomos no estaban sorprendidos porque estaban concentrados en un concurso de programación), la misión se torció y los monos voladores cayeron. se estrellaron. Los monos se han estrellado en medio de una densa selva, y están separados unos de otros. entre sí.

Por suerte, los walkie-talkies han sobrevivido al accidente y uno de los monos de fuera ha podido subir a un árbol muy alto para inspeccionar la zona. El mono explorador informa de la disposición de la selva como una cuadrícula rectangular, en la que cada celda es un mono superviviente del accidente o una parcela de bosque denso.

Cada parcela tiene un dígito asociado, que representa la fuerza mínima del machete necesario para que los monos la atraviesen. Los monos son capaces de pasar a través de parcelas adyacentes que están cortadas y pueden cortar a través de una parcela adyacente si tienen el machete con la fuerza necesaria. Las parcelas son adyacentes si comparten un lado completo, no sólo una esquina. Un mono puede escapar de la jungla si es capaz de moverse fuera de ella.

Tarea

Los monos deben salir de la selva lo antes posible. Tienen a su disposición varios machetes de diferente potencia. Cada mono recibirá un machete de fuerza ~s~. ¿Puedes determinar el mínimo ~s~ para que todos los monos puedan escapar de la selva (de modo que los machetes restantes puedan reservarse para cortar gnomos)?

Entrada

La primera línea de cada escenario contiene dos enteros, ~n~ y ~m~ ~(3 \le n \le 1.000; 3 \le m \le 1.000)~, que representan el número de filas y columnas de la selva, respectivamente. Las ~n~ líneas siguientes constan cada una de una sola cadena de ~m~ dígitos. Un dígito es ~0~ si contiene la posición de un mono, y ~1-9~ en caso contrario. Se garantiza que los bordes de la selva no contienen monos, y que hay al menos un mono en la selva.

Salida

Para cada escenario, la salida de una sola línea que contiene un solo número entero, la respuesta al problema.

Ejemplo de Entrada #1

6 8
22211111
20211011
31114455
11110445
11110405
11119145

Ejemplo de Salida #1

4

Ejemplo de Entrada #2

10 9
111111111
100111011
110011001
110111001
111111011
111111111
100110011
100101111
111101111
111111111

Ejemplo de Salida #2

1

Ejemplo de Entrada #3

3 3
123
405
679

Ejemplo de Salida #3

2