Powszechnie wiadomo, że gdy koty wchodzą do pustych naczyń, wykazują właściwości cieczy.
Matematyk Pietrow często obserwował to zjawisko na przykładzie swoich kotów, a nawet przeprowadził serię eksperymentów, konstruując różne rodzaje naczyń i umieszczając w nich koty. Okazało się, że koty zawsze wybierają pozycję tak niską, jak to tylko możliwe, a dokładniej – minimalizują poziom najwyższego punktu swojego ciała. W przypadku kilku zagłębień w naczyniu, koty wybierają to najniższe, ale tylko spośród tych, w których byłyby w stanie się zmieścić.
Genialna myśl przyszła do głowy Pietrowowi: w rzeczywistości koty mogą być używane jako komputery analogowe do rozwiązywania niektórych problemów optymalizacji kwantowej! Aby sprawdzić swoją hipotezę, matematyk Pietrow opracował następujący model matematyczny:
Wyobraźmy sobie naczynie jako tabelę $T$ o rozmiarze $n \times m$. Niektóre komórki to ściany, reszta komórek jest pusta. Umieszczenie kota w naczyniu jest optymalne, jeśli spełnione są następujące warunki:
- Kot zajmuje kilka pustych komórek. Wszystkie komórki zajmowane przez kota tworzą spójny kształt złożony z $k$ komórek. Kształt jest spójny, jeśli każdą z jego komórek można osiągnąć z dowolnej innej komórki, poruszając się przez sąsiadujące bocznie komórki (przy czym wszystkie komórki pośrednie również muszą być zajęte przez kota).
- Poziom najwyższej komórki $h$ zajmowanej przez kota powinien być tak niski, jak to możliwe. Wiersze tabeli są numerowane od $1$ do $n$, a wiersz jest wyżej, jeśli jego numer jest mniejszy.
Niestety, matematyk Pietrow nie jest biegły w programowaniu. Prosi Cię o wyznaczenie numeru wiersza najwyższej komórki $h$ zajmowanej przez kota dla danej tabeli $T$ oraz objętości kota $k$.
Wejście
Pierwsza linia zawiera liczby całkowite $n$, $m$ oraz $k$ ($1 \le n, m \le 1000$, $1 \le k \le 10^6$).
Kolejne $n$ linii zawiera po $m$ symboli — opis tabeli $T$. $j$-ty symbol $i$-tego wiersza odpowiada komórce na przecięciu $i$-tego wiersza i $j$-tej kolumny tabeli $T$. „#” oznacza, że ta komórka jest ścianą, a „.” oznacza, że ta komórka jest pusta.
Wyjście
Wypisz numer wiersza, który zawiera najwyższą zajętą komórkę dla dowolnego optymalnego umieszczenia kota. Jeśli kota nie da się umieścić w naczyniu, wypisz „-1” (bez cudzysłowów).
Przykład
Wejście 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
Wyjście 1
4
Wejście 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
Wyjście 2
2
Wejście 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
Wyjście 3
2
Uwagi
Optymalne umieszczenie kota dla każdego z przykładów może wyglądać następująco:
