불의 산

아제르바이잔(올해 국제정보올림피아드 개최국)의 불의 산 Yanar Dag으로 소풍을 갔다가 길을 잃었다! 산은 $R$개의 행과 $C$개의 열로 이루어진 격자 모양이다. 당신은 격자의 왼쪽 위에 있으며, 오른쪽 아래에 있는 소풍 버스로 이동하려고 한다. 버스가 곧 출발하므로 가능한 한 빨리 그곳에 도착하고 싶다. 버스에 가기 위해 현재 있는 칸의 바로 위, 오른쪽, 아래 또는 왼쪽 칸으로 이동할 수 있다.

하지만 불의 산에는 산에서 새어 나오는 천연가스로 인해 생긴 여러 개의 불꽃이 있다. 당신은 아주 멋진 옷을 입고 있으므로 필요 이상으로 많은 불꽃을 통과해 달리고 싶지 않다. 더 구체적으로, 버스로 가는 길에 최대 $K$개의 불꽃을 통과할 의향이 있다.

당신의 과제는 최대 $K$개의 불꽃을 통과할 수 있을 때 얼마나 빨리 버스로 이동할 수 있는지 계산하는 것이다.

채점

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| 이 그룹은 $K = 0$인 테스트 케이스 하나로 구성되며, 이는 우리 포스터(https://www.progolymp.se/2019/affish2018.pdf)에 있는 것이다.

$2$ |$7$| 항상 버스에 도달할 수 있으며, 격자에서 아래쪽이나 오른쪽으로만 이동하면 된다.

$3$ |$15$| $K = 0$이고, 각 열은 열의 위쪽에서 시작하는 불기둥 하나와 열의 아래쪽에서 시작하는 불기둥 하나로 구성된다. 기둥의 길이는 $0$일 수 있으며, 각 열에는 항상 불이 없는 칸이 적어도 하나 있다.

$4$ |$10$| $K = 0$

$5$ |$19$| $K = 1$

$6$ |$29$| 추가 제한이 없다.

예제

테스트 케이스 그룹 $2$에는 예제 $1$만 나올 수 있고, 테스트 케이스 그룹 $3$에는 예제 $4$만 나올 수 있음에 유의하라.

첫째 줄에 세 정수 $R, C, K$ ($2 \le R, C \le 100$, $0 \le K \le 200$)가 주어진다. 각각 불의 산을 이루는 격자의 행 수와 열 수, 그리고 통과해 달릴 수 있는 불꽃의 수를 나타낸다.

다음 $R$개의 줄에는 불의 산의 모습에 대한 설명이 주어진다. 이 중 $i$번째 줄에는 $i$번째 행의 모습을 나타내는 $C$개의 문자가 주어진다. 각 문자는 칸이 비어 있으면 점(.)이고, 칸에 불꽃이 있으면 사각형(#)이다. 왼쪽 위 칸과 오른쪽 아래 칸은 항상 점이다.

버스에 도달하는 데 필요한 최소 이동 횟수인 정수 $N$을 출력한다. $K$개보다 많은 불꽃을 통과하지 않고는 목적지에 도달할 수 없다면 ```nej`''을 출력한다.