트럭 디젤 운송

디젤 트럭이 출발지에서 목적지까지 디젤을 실어 나른다. 트럭에는 별도 연료 탱크가 없고, 적재한 디절이 곧 연료다. 출발지에서 목적지까지 도중에 연료를 다 쓰지 않고 운반할 수 있는 디젤의 최대 리터 수를 구하라. 주어진 연료로 목적지에 도달할 수 없으면 $-1$을 출력한다.

지형은 $m$행 $n$열 격자로 주어지며, 각 칸의 고도는 미터 단위 정수이고 $0$ 이상 $4000$ 이하이며 $100$의 배수다. 첫 행이 북쪽, 마지막 행이 남쪽, 첫 열이 서쪽, 마지막 열이 동쪽이다. 트럭은 북서쪽 모서리 $(0, 0)$에서 출발해 남동쪽 모서리 $(m-1, n-1)$로 간다. 한 번에 동, 남, 서 인접 칸으로만 이동할 수 있으며 북쪽이나 대각선 이동은 불가하다.

디젤 1리터의 질량은 $1.0$ kg이다. 평지나 내리막 한 칸 이동에는 $10$리터가 든다. 오르막 한 칸에서는 기본 $10$리터에 더해, 그 구간 시작 시점 총 질량의 톤 수(질량을 $1000$ kg 단위로 내림)마다 고도 차 $100$ m당 $4$리터가 추가로 든다. 예를 들어 구간 시작 질량이 $26010$ kg이고 고도가 $400$ m에서 $700$ m로 오르면 $10 + 3 \times 4 \times 26 = 322$리터가 필요하다.

각 이동 직전에 정수 리터만큼 디젤을 버릴 수 있다. 공차 중량은 $8$톤($8000$ kg)이고, 출발 시 디젤은 $25000$리터다.

첫 줄에 $m$, $n$이 주어진다. 다음 $m$줄에 격자 고도가 주어진다. 고도는 $0$ 이상 $4000$ 이하이며 $100$의 배수다.

운반할 수 있는 디젤의 최대 리터 수를 출력한다. 목적지에 빈 탱크로 도착하면 $0$이다. 도달할 수 없으면 $-1$이다.