Es bien sabido que cuando los gatos entran en recipientes huecos, demuestran propiedades de un líquido.
El matemático Petrov observó a menudo este fenómeno con sus gatos e incluso llevó a cabo una serie de experimentos construyendo diferentes tipos de recipientes y colocando gatos en ellos. Resultó que los gatos siempre eligen su posición para estar lo más bajo posible, más precisamente, para minimizar el nivel del punto más alto de su cuerpo. En caso de haber varios huecos en el recipiente, los gatos eligen el más bajo, pero solo entre aquellos en los que cabrían.
A Petrov se le ocurrió una idea brillante: de hecho, ¡los gatos pueden usarse como computadoras analógicas para resolver algunos problemas de optimización cuántica! Para comprobar su hipótesis, el matemático Petrov desarrolló el siguiente modelo matemático:
Imaginemos un recipiente como una tabla $T$ de tamaño $n \times m$. Algunas celdas son paredes, el resto de las celdas están vacías. Una colocación de un gato en el recipiente es óptima si se cumplen las siguientes condiciones:
- El gato ocupa varias celdas vacías. Todas las celdas ocupadas por el gato forman una figura conectada de $k$ celdas. Una figura está conectada si cada una de sus celdas puede alcanzarse desde cualquier otra celda moviéndose a través de celdas adyacentes lateralmente (y todas las celdas de transición también están ocupadas por el gato).
- El nivel de la celda más alta $h$ ocupada por el gato debe ser lo más bajo posible. Las filas de la tabla están numeradas de $1$ a $n$ y una fila es más alta si su número es menor.
Desafortunadamente, el matemático Petrov no tiene habilidades en programación. Te pide que determines la altura de la celda más alta $h$ ocupada por un gato para una tabla $T$ dada y un volumen de gato $k$.
Entrada
La primera línea contiene los enteros $n$, $m$ y $k$ ($1 \le n, m \le 1000$, $1 \le k \le 10^6$).
Las siguientes $n$ líneas contienen $m$ símbolos cada una, representando una descripción de la tabla $T$. El $j$-ésimo símbolo de la $i$-ésima fila corresponde a una celda en la intersección de la fila $i$ y la columna $j$ de $T$. “#” significa que esta celda es una pared, y “.” significa que esta celda está vacía.
Salida
Imprime el número de la fila que contiene la celda más alta ocupada para cualquier colocación óptima de un gato. Si un gato no puede colocarse en el recipiente, imprime “-1” (sin comillas).
Ejemplos
Entrada 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
Salida 1
4
Entrada 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
Salida 2
2
Entrada 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
Salida 3
2
Nota
Una colocación óptima de un gato para cada ejemplo puede ser la siguiente:
