삼림 벌채

문제

JOI 왕국에는 광대한 삼림이 있다. 삼림은 직사각형 모양이며, 남북으로 $H$ 칸, 동서로 $W$ 칸의 격자 모양으로 나뉘어 있다. 북쪽에서 $i$ 번째 칸, 서쪽에서 $j$ 번째 칸($1\,\,\le\,\,i\,\,\le\,\,H,\,1\,\,\le\,\,j\,\,\le\,\,W$)의 구역에는 $A_{i,j}$ 그루의 나무가 자라고 있다. 단, 북서쪽 끝 구역에는 목재 가공 공장이 있어서 나무가 자라고 있지 않다. 즉, $A_{1,1}=0$ 이다.

나무가 자라고 있지 않은 구역에는 사람이 들어갈 수 있다. 또한 사람은 동서남북으로 인접한 구역에 그 구역에 나무가 자라고 있지 않다면 이동할 수 있다. 삼림 밖으로 나갈 수는 없다. JOI 군은 JOI 왕국의 공공사업으로서 나무를 베어, 북서쪽 끝 구역과 남동쪽 끝 구역을 서로 오갈 수 있게 하고 싶다.

나무를 베는 것은 다음과 같이 이루어진다. 처음에 JOI 군은 목재 가공 공장이 있는 북서쪽 끝 구역에 있다. JOI 군은 현재 있는 구역과 동서남북으로 인접한, 나무가 자라고 있지 않은 구역으로 $1$ 분 만에 이동할 수 있다. 또한 동서남북으로 인접한, 나무가 자라고 있는 구역에서 $1$ 분 만에 나무를 $1$ 그루 벨 수 있다. 단, 나무를 $1$ 그루 베면 그때마다 북서쪽 끝 구역에 있는 목재 가공 공장까지 벤 나무를 운반해야 한다. 나무를 운반하는 동안에도 JOI 군의 이동 속도는 변하지 않는다. 나무를 운반하는 동안에는 다른 나무를 벨 수 없다.

조건을 만족하도록 나무를 베는 데 걸리는 시간의 최솟값을 구하시오. 단, 베는 데 걸리는 시간이란 마지막으로 벤 나무를 목재 가공 공장까지 운반할 때까지의 시간으로 한다.

제한

• $1\,\,\le\,\,H\,\,\,\le\,\,30$
• $1\,\,\le\,\,W\,\,\le\,\,30$
• $(H,\,W)\,\,\neq\,\,(1,\,1)$
• $0\,\,\le\,\,A_{i,j}\,\,\le\,\,10000$ ($1\,\,\le\,\,i\,\,\le\,\,H,\,1\,\,\le\,\,j\,\,\le\,\,W$)
• $A_{1,1}=0$

서브태스크

서브태스크 1 [15점]

• $1\,\,\le\,\,H\,\,\le\,\,5$
• $1\,\,\le\,\,W\,\,\le\,\,5$

서브태스크 2 [28점]

• $A_{i,j}\,\,\le\,\,A_{i,j+1}$ ($1\,\,\le\,\,i\,\,\le\,\,H,\,1\,\,\le\,\,j\,\,\le\,\,W-1$)
• $A_{i,j}\,\,\le\,\,A_{i+1,j}$ ($1\,\,\le\,\,i\,\,\le\,\,H-1,\,1\,\,\le\,\,j\,\,\le\,\,W$)

서브태스크 3 [57점]

• 추가 제약이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$H$ $W$
$A_{1,1}$ $...$ $A_{1,W}$
:
$A_{H,1}$ $...$ $A_{H,W}$

출력
조건을 만족하도록 나무를 베는 데 걸리는 시간의 최솟값을 $1$ 줄로 출력한다.

예제 입력 1

2 3
0 1 2
3 4 5

예제 출력 1

32

북쪽에서 $i$ 번째 칸, 서쪽에서 $j$ 번째 칸의 구역을 $(i,\,j)$ 로 나타낸다.

먼저 $(1,\,2)$ 의 나무를 벤다. 여기에는 $1$ 분이 걸린다.

다음으로 $(1,\,3)$ 의 나무를 모두 벤다. $1$ 그루를 베는 데에는 $(1,1)$ 에서 동쪽으로 $1$ 칸 나아가 $(1,\,3)$ 의 나무를 베고, 서쪽으로 $1$ 칸 나아가 $(1,1)$ 로 돌아오면 되므로 $3$ 분이 걸린다. 따라서 여기에는 $2\,\,\times\,\,3\,=\,6$ 분이 걸린다.

다음으로 $(2,\,3)$ 의 나무를 모두 벤다. $1$ 그루를 베는 데에는 $(1,1)$ 에서 동쪽으로 $2$ 칸 나아가 $(2,\,3)$ 의 나무를 베고, 서쪽으로 $2$ 칸 나아가 $(1,1)$ 로 돌아오면 되므로 $5$ 분이 걸린다. 따라서 여기에는 $5\,\,\times\,\,5\,=\,25$ 분이 걸린다.

전부 합쳐 $1\,+\,6\,+\,25\,=\,32$ 분이 걸린다. 이보다 적은 시간으로 조건을 만족하도록 나무를 벨 수는 없으므로 $32$ 를 출력한다.

예제 입력 2

2 5
0 5 0 0 0
0 0 0 9 1

예제 출력 2

13

$(2,\,5)$ 의 나무만 베면 된다.

예제 입력 3

2 5
0 2 0 0 0
0 0 0 9 1

예제 출력 3

11

먼저 $(1,\,2)$ 의 나무를 베고, 다음으로 $(2,\,5)$ 의 나무를 베면 된다.