협곡 건너기

다리와 통로 건설자들은 이 지역 산맥에 새로운 길을 내는 일을 맡고 있다. 그들은 당신이 가장 좋아하는 협곡에 새 경로를 만드는 계획을 승인했다. 신나는 마음으로 이 아름다운 새 경로를 만들기 시작했지만, 근처 강의 흐름을 고려하지 않았다는 사실을 깨닫는다. 협곡이 범람한 것이다. 아주 드물게 일어나는 일이지만, 경로의 일부를 지나갈 수 없게 만든다. 그래서 경로에서 가장 낮은 지점이 최대한 높아지도록 경로를 만들려고 한다. 마을로 돌아가 가진 돈을 모두 써서 밧줄 다리를 산다. 이 다리로 협곡에서 가장 낮은 부분을 우회할 계획이다.

그림 C.1: 샘플 입력 1에 대한 협곡과 최소 높이가 1, 2인 두 가지 경로. B는 다리를 나타낸다.

협곡 지도는 직사각형 격자로 이루어져 있고, 각 칸에는 그 칸 지형의 높이가 적혀 있다. 경로는 협곡의 남쪽(지도의 아래쪽)에서 북쪽(지도의 위쪽)으로 이어지는 칸들의 연결된 나열을 지난다. 두 칸은 변을 공유할 때만 연결되어 있다고 본다. 특히 대각선으로 맞닿은 두 칸은 연결된 것으로 보지 않는다. 따라서 지도 가장자리에 있지 않은 칸은 4개의 다른 칸과 연결되어 있다. 그림 C.1의 왼쪽에 첫 번째 샘플 입력의 지도가 있다.

협곡을 지나는 경로는 격자의 아래쪽 칸 아무 곳에서 시작하고 위쪽 줄의 아무 칸에서 끝날 수 있다. 그림 C.1의 오른쪽에 있는 두 경로가 그러하다. 최소 높이는 경로가 지나는 모든 칸 중 가장 낮은 높이로 정해진다. 다리 하나는 정확히 한 칸을 건너는 데 쓸 수 있다. 이 칸은 경로의 최소 높이를 계산할 때 고려하지 않는다. 여러 다리를 연속으로 이어 여러 칸을 건너는 데 쓰는 것도 허용된다.

협곡 지도와 사용할 수 있는 다리의 개수가 주어질 때, 최적 경로의 최소 높이를 구하라.

• 한 줄에 세 정수 1 ≤ R ≤ 1000, 1 ≤ C ≤ 1000(지도의 크기)과 0 ≤ K ≤ R − 1(지을 수 있는 다리의 개수)가 주어진다.
• 이어서 R개의 줄이 주어지고, 각 줄에는 C개의 정수가 있다. i번째 줄의 j번째 정수는 지점 (i, j)의 협곡 높이 0 ≤ H_{i,j} ≤ 10^9이다. 첫 번째 줄은 협곡의 북쪽 가장자리, 마지막 줄은 남쪽 가장자리에 해당한다.

최적 경로의 최소 높이를 나타내는 정수 하나를 출력한다.