백만장자의 금고 소동

빚에 시달리는 오리 친구가 도움을 청했다. 이 일을 해내면 친구는 빚을 모두 갚을 수 있다. 친구의 삼촌은 엄청난 부자 오리인데, 금고 안을 동전 산으로 가득 채워 두었다. 삼촌에게는 그중 유난히 아끼는 동전이 한 닢 있고, 평소에는 벨벳 방석 위 유리 덮개 아래에 둔다.

얼마 전 금고 안의 동전을 옮기다가 이 동전이 실수로 동전 더미 속에 섞여 들어갔다. 위치는 이미 찾아냈지만, 하필 금고 입구에서 대각선 반대쪽 구석이고 동전 산에 막혀 있어서 다가가기가 쉽지 않다.

삼촌은 장비를 직접 챙겨 온다는 조건으로, 동전을 가져오면 친구에게 돈을 주겠다고 했다. 친구는 사다리를 사기로 했다. 사다리가 길수록 더 높은 절벽을 오를 수 있지만 값도 비싸므로, 동전까지 갈 수 있는 가장 짧은 사다리를 사려고 한다.

금고는 동전 더미의 높이를 미터 단위로 적은 직사각형 격자다. 입구는 북서쪽 구석에 있고, 친구는 그 칸의 높이에서 출발한다. 특별한 동전은 남동쪽 구석에 있다. 친구는 어떤 칸에서 바로 북쪽, 서쪽, 남쪽, 동쪽에 붙어 있는 칸으로 이동한다. 뛰거나 날지 못하므로 $n$미터를 올라가려면 길이가 $n$미터 이상인 사다리가 필요하다. 내려가는 것은 높이 차이가 아무리 커도 대가가 없다. 중력이 대신 해 주기 때문이다.

북서쪽 구석에서 남동쪽 구석까지 갈 수 있는 가장 짧은 사다리의 길이를 구하라.

첫째 줄에 금고의 세로 길이 $M$과 가로 길이 $N$이 주어진다 ($1 \le M, N \le 1000$).

다음 $M$개 줄에는 각각 정수가 $N$개씩 주어진다. 그중 $i$번째 줄의 $j$번째 정수는 $i$행 $j$열에 쌓인 동전 더미의 높이다. 첫 줄은 가장 북쪽 칸을 서쪽부터 동쪽 순서로, 마지막 줄은 가장 남쪽 칸을 서쪽부터 동쪽 순서로 나타낸다. 모든 높이 $h$는 $0 \le h \le 10^9$을 만족한다.

북서쪽 구석에서 남동쪽 구석까지 갈 수 있는 가장 짧은 사다리의 길이를 미터 단위 정수 하나로 출력한다.