Il est bien connu que lorsque les chats entrent dans des récipients creux, ils démontrent les propriétés d'un liquide.
Le mathématicien Petrov a souvent observé ce phénomène avec ses propres chats et a même mené une série d'expériences en construisant différents types de récipients pour y placer ses chats. Il s'est avéré que les chats choisissent toujours leur position pour être aussi bas que possible, plus précisément, pour minimiser le niveau du point le plus élevé de leur corps. Dans le cas de plusieurs creux dans le récipient, les chats choisissent le plus bas, mais uniquement parmi ceux dans lesquels ils peuvent tenir.
Une idée brillante est venue à l'esprit de Petrov : en fait, les chats peuvent être utilisés comme des ordinateurs analogiques pour résoudre certains problèmes d'optimisation quantique ! Pour vérifier son hypothèse, le mathématicien Petrov a développé le modèle mathématique suivant :
Imaginons un récipient comme une grille $T$ de taille $n \times m$. Certaines cellules sont des murs, le reste des cellules sont vides. Un placement d'un chat dans le récipient est optimal si les conditions suivantes sont remplies :
- Le chat occupe plusieurs cellules vides. Toutes les cellules occupées par le chat forment une forme connexe de $k$ cellules. Une forme est connexe si chacune de ses cellules peut être atteinte depuis n'importe quelle autre cellule en se déplaçant à travers des cellules adjacentes (et toutes les cellules de transition sont également occupées par le chat).
- Le niveau de la cellule la plus élevée $h$ occupée par le chat doit être aussi bas que possible. Les lignes de la grille sont numérotées de $1$ à $n$ et une ligne est considérée comme plus élevée si son numéro est plus petit.
Malheureusement, le mathématicien Petrov n'est pas doué en programmation. Il vous demande de déterminer la hauteur de la cellule la plus élevée $h$ occupée par un chat pour une grille $T$ donnée et un volume de chat $k$.
Entrée
La première ligne contient les entiers $n$, $m$ et $k$ ($1 \le n, m \le 1000$, $1 \le k \le 10^6$).
Les $n$ lignes suivantes contiennent chacune $m$ symboles — une description de la grille $T$. Le $j$-ième symbole de la $i$-ième ligne correspond à une cellule à l'intersection de la $i$-ième ligne et de la $j$-ième colonne de $T$. « # » signifie que cette cellule est un mur, et « . » signifie que cette cellule est vide.
Sortie
Affichez le numéro de la ligne qui contient la cellule la plus élevée occupée pour tout placement optimal d'un chat. Si un chat ne peut pas être placé dans le récipient, affichez « -1 » (sans les guillemets).
Exemples
Entrée 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
Sortie 1
4
Entrée 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
Sortie 2
2
Entrée 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
Sortie 3
2
Remarque
Un placement optimal d'un chat pour chaque exemple peut être le suivant :
