고양이가 빈 그릇에 들어가면 액체와 같은 성질을 보인다는 것은 잘 알려진 사실입니다.
수학자 페트로프는 자신의 고양이를 관찰하며 다양한 종류의 그릇을 만들고 그 안에 고양이를 넣어보는 일련의 실험을 수행했습니다. 고양이는 항상 자신의 위치를 가능한 한 낮게, 더 정확히 말하면 몸의 가장 높은 지점의 높이를 최소화하는 위치를 선택한다는 사실을 발견했습니다. 그릇에 여러 개의 구덩이가 있는 경우, 고양이는 들어갈 수 있는 구덩이 중에서 가장 낮은 곳을 선택합니다.
페트로프의 머릿속에 기발한 생각이 떠올랐습니다. 사실 고양이는 양자 최적화 문제를 해결하기 위한 아날로그 컴퓨터로 사용될 수 있다는 것입니다! 자신의 가설을 검증하기 위해 수학자 페트로프는 다음과 같은 수학적 모델을 개발했습니다.
그릇을 $n \times m$ 크기의 표 $T$라고 가정해 봅시다. 일부 칸은 벽이고, 나머지 칸은 비어 있습니다. 다음 조건을 만족할 때 고양이의 배치를 최적이라고 합니다:
- 고양이는 여러 개의 빈 칸을 차지합니다. 고양이가 차지하는 모든 칸은 $k$개의 칸으로 이루어진 연결된 형태를 이룹니다. 연결된 형태란, 고양이가 차지한 칸들 사이에서 인접한 칸들을 통해 이동하여 서로 도달할 수 있는 상태를 의미합니다(이동 경로상의 모든 칸 또한 고양이가 차지하고 있어야 합니다).
- 고양이가 차지하는 가장 높은 칸의 높이 $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$번째 문자는 $T$의 $i$번째 행과 $j$번째 열이 교차하는 칸에 해당합니다. "#"은 해당 칸이 벽임을 의미하고, "."은 해당 칸이 비어 있음을 의미합니다.
출력
고양이를 최적으로 배치했을 때 가장 높은 칸이 위치한 행 번호를 출력하십시오. 고양이를 그릇에 배치할 수 없는 경우 "-1"을 출력하십시오(따옴표 제외).
예제
예제 입력 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
예제 출력 1
4
예제 입력 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
예제 출력 2
2
예제 입력 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
예제 출력 3
2
참고
각 예제에 대한 고양이의 최적 배치는 다음과 같을 수 있습니다:
