002 - 森林伐採 （Deforestation）

問題

JOI 王国には広大な森林がある．森林は長方形の形をしており，南北に H マス，東西に W マスのマス目状に分けられている．北から i マス目，西から j マス目(1 ≦ i ≦ H, 1 ≦ j ≦ W)の領域には A_{i, j} 本の木が生えている．ただし，北西の端の領域には木材加工工場があり，木が生えていない．すなわち，A_1,1=0 である．

木が生えていない領域には人が立ち入ることが出来る．また人は東西南北に隣接する領域に，その領域に木が生えていなければ，移動することができる．森林の外に出ることはできない．JOI 君は JOI 王国の公共事業として，木を伐採し，北西の端の領域と南東の端の領域を，相互に行き来可能にしたい．

木の伐採は以下のようにして行う．はじめ，JOI 君は木材加工工場のある北西の端の領域にいる．JOI 君は，現在いる領域と東西南北に隣接する木の生えていない領域に 1 分で移動することができる．また，東西南北に隣接する木の生えている領域から，1 分で木を 1 本伐採することができる．ただし，木を 1 本伐採したら，そのたびに北西の端の領域にある木材加工工場まで伐採した木を運ばなければならない．木を運んでいる間も，JOI 君の移動速度は変わらない．木を運んでいる間は，他の木を伐採することはできない．

条件を満たすように木を伐採するのにかかる時間の最小値を求めよ．ただし，伐採にかかる時間とは，最後に伐採した木を，木材加工工場に運ぶまでの時間とする．

制約

• 1 ≦ H ≦ 30
• 1 ≦ W ≦ 30
• (H, W) ≠ (1, 1)
• 0 ≦ A_{i, j} ≦ 10000 (1 ≦ i ≦ H, 1 ≦ j ≦ W)
• A_{1, 1}=0

入力

入力は以下の形式で標準入力から与えられる．

H W
A1,1 ... A1,W
:
AH,1 ... AH,W

小課題 2 [28点]

• A_{i, j} ≦ A_{i, j+1} (1 ≦ i ≦ H, 1 ≦ j ≦ W-1)
• A_{i, j} ≦ A_{i+1, j} (1 ≦ i ≦ H-1, 1 ≦ j ≦ W)

小課題 3 [57点]

• 追加の制限はない．

入出力例

入力例 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 × 3 = 6 分かかる．

次に (2, 3) の木をすべて伐採する．1 本伐採するのに，(1,1) から東に 2 マス進み，(2, 3) の木を伐採し，西に 2 マス進んで (1,1) に戻ればいいので， 5 分かかる．よってこれには 5 × 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) の木を伐採すればよい．