33907번 - 투명 스프레이

문제

월급 루팡 정민이는 일을 하지 않기 위해 사람들을 피해서 퇴근하려 한다.

건물은 $N \times M$ 크기의 격자로 구성되어 있고, 격자 $(i, j)$에서 사람을 만날 위험도는 $F_{ij}$이다. 정민이는 좌측 상단 $(1, 1)$에서 우측 하단 $(N, M)$으로 이동해야 한다.

이동은 상하좌우 인접 칸으로만 가능하며, 만약 이동하려는 칸의 위험도가 $X$ 초과라면 해당 칸을 지나기 위해선 투명 스프레이가 필요하다. 시작 칸 $(1, 1)$의 위험도는 항상 0ドル$이다.

정민이는 칼퇴를 위해 투명 스프레이를 $K$개 구비해 두었다. 투명 스프레이를 하나 사용하여 한 칸의 위험도를 무시하고 지나갈 수 있고, 스프레이가 적용된 칸의 효과는 재방문해도 유지된다.

퇴근 경로 상에서 투명 스프레이 사용 횟수가 $K$ 이하가 되도록 하는 최소의 위험도 $X$를 구하라. 단, 위험도는 음이 아닌 정수이다.

입력

첫 번째 줄에 세 정수 $N,ドル $M,ドル $K$가 주어진다. $(2 \leq N,M \leq 700;$ 0ドル \leq K \leq 1,400円)$

그 다음 $N$개의 줄에 걸쳐, 각 줄에 $M$개의 정수 $F_{ij}$가 주어진다. (0ドル \leq F_{ij} \leq 10^9$)

출력

첫 번째 줄에 문제의 정답을 출력한다. $X$의 값에 상관없이 퇴근이 불가능한 경우에는 $-1$을 출력한다.

제한

힌트