그냥 지나가기만

Justin과 Fred는 주의 서쪽에서 동쪽으로 자동차 여행을 떠난다. 그들에게는 몇 가지 도로 여행 규칙이 있다.

1. 아주 즐거운 시간을 보내야 한다!
2. 여행은 주의 서쪽 경계 어딘가에서 시작해 동쪽 경계 어딘가에서 끝나야 한다.
3. 여행의 각 이동은 정동, 북동 대각선, 남동 대각선 중 하나여야 한다.
4. 정확히 n개의 "고개"(아래에 정의)를 지나야 한다.
5. Fred는 높은 고도에 민감하기 때문에 여행 중 고도의 누적 합을 최소화하려고 한다.
6. 아주 즐거운 시간을 보내야 한다!

Justin과 Fred는 동쪽으로 이동하므로, "고개"란 동쪽과 서쪽의 고도가 엄격히 더 낮고 북쪽과 남쪽의 고도가 엄격히 더 높은 모든 지점을 말한다. 그림 E.1의 고도 지도를 보자. 운전할 수 없는 지점(물이거나 주 경계를 벗어나지 않으려는 고집 때문)은 검은색으로, 고개는 회색으로 표시되어 있다. 경계나 운전할 수 없는 지점에 인접한 지점은 고개로 간주되지 않는다.

그림 E.1: 고도 지도 예시

입력은 세 정수 r c n으로 시작한다. 이는 주의 지형을 나타내는 격자의 행 수와 열 수(3 ≤ r, c ≤ 500), 그리고 지나야 하는 고개의 정확한 수(0 ≤ n ≤ 10)를 나타낸다. 다음 r개 줄에는 각각 c개의 고도 값이 주어진다. 운전할 수 없는 지점은 −1로, 나머지 고도는 0과 1 000 사이의 값이다. 동쪽 경계와 서쪽 경계에는 운전할 수 있는 지점이 각각 하나 이상 있음이 보장된다.

도로 여행 규칙을 만족하는 최적 경로를 따라 이동할 때 고도의 합을 출력한다. 그러한 경로가 없으면 impossible을 출력한다.