액체 고양이

고양이가 속이 빈 그릇에 들어가면 액체처럼 행동한다는 것은 잘 알려져 있다.

수학자 페트로프는 자기 고양이를 보며 이 현상을 자주 관찰했고, 여러 모양의 그릇을 만들어 고양이를 넣는 실험을 여러 번 했다. 고양이는 항상 몸의 가장 높은 지점이 가능한 한 낮아지도록, 즉 그 높이를 최소화하는 위치를 고른다는 사실이 밝혀졌다. 그릇에 여러 개의 움푹한 곳이 있으면 고양이는 그중 가장 낮은 곳을 고르는데, 들어갈 수 있는 곳만 고려한다.

페트로프는 문득 이런 생각을 했다. 고양이를 아날로그 컴퓨터로 써서 양자 최적화 문제를 풀 수 있지 않을까? 이 가설을 확인하려고 페트로프는 다음과 같은 수학적 모델을 만들었다.

그릇을 $n \times m$ 크기의 표 $T$로 나타내자. 일부 칸은 벽이고 나머지 칸은 비어 있다. 그릇에서 고양이의 배치가 최적이라는 것은 다음 조건을 만족한다는 뜻이다.

1. 고양이는 비어 있는 여러 칸을 차지한다. 고양이가 차지한 모든 칸은 $k$개의 칸으로 이루어진 연결된 모양을 이룬다. 어떤 모양이 연결되어 있다는 것은, 각 칸에서 다른 모든 칸으로 변을 공유하는 인접 칸을 통해 이동할 수 있다는 뜻이다. 이동 경로에 있는 칸도 모두 고양이가 차지하고 있어야 한다.
2. 고양이가 차지한 칸 중 가장 높은 칸의 행 번호 $h$가 가능한 한 작아야 한다. 표의 행은 $1$부터 $n$까지 번호가 매겨지며, 행 번호가 작을수록 더 높다.

안타깝게도 페트로프는 프로그래밍에 능숙하지 않다. 그는 표 $T$와 고양이의 부피 $k$가 주어졌을 때 고양이가 차지한 가장 높은 칸의 높이 $h$를 구해 달라고 부탁한다.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다. ($1 \le n,m \le 1000$, $1 \le k \le 10^6$)

다음 $n$개의 줄에는 각각 $m$개의 문자가 주어지며 표 $T$를 나타낸다. $i$번째 줄의 $j$번째 문자는 $i$번째 행과 $j$번째 열이 만나는 칸에 대응한다. "\#"는 그 칸이 벽이라는 뜻이고 "."는 그 칸이 비어 있다는 뜻이다.

어떤 최적 배치에서든 고양이가 차지한 가장 높은 칸이 있는 행의 번호를 출력한다. 고양이를 그릇에 넣을 수 없으면 "-1"을 출력한다.

각 예제에서 고양이의 최적 배치는 다음 그림과 같을 수 있다.