1229 - Minimizing Fatigue

時間制限 2 秒 / メモリ制限 256 MB / 得点 100 / Writer もけ / x 3 / 統計 /

TLE
2sec
MLE
256MB
得点
100

問題

もけちゃんはYDK王国に居住している。
YDK王国は長方形の形をしており、南北に $H$ マス、東西に $W$ マスのマス目状に区切られている。北から $i$ マス目、西から $j$ マス目 $(1 \le i \le H, 1 \le j \le W)$ の土地には、土地の険しさ $c_{i, j}$ が与えられている。

国王YDKに仕えることになったもけちゃんは、国王YDKのいるお城へ向かおうと考えている。最初、もけちゃんはYDK王国の北西の端の土地にいる。もけちゃんは現在いる土地と東西南北に隣接する土地への移動を繰り返して、南東の端の土地に位置しているお城へと向かう。ただし、一回の移動に要する距離は $1$ とする。

もけちゃんはできる限り疲れたくない。国王YDKも疲れた果てたもけちゃんを見たくはない。そこで、できる限り疲労度のかからないルートを用いることにした。
疲労度を (お城にたどり着くまでに要する距離)$\times$(通過した土地の険しさの総和) としたときの疲労度の最小値を求めよ。

入力

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

$H$ $W$
$c_{1, 1}$ $\cdots$ $c_{1, W}$
$\vdots$
$c_{H, 1}$ $\cdots$ $c_{H, W}$

出力

疲労度の最小値を一行で出力せよ。出力の末尾に改行を入れること。

制約

  • $2 \le H \le 50$
  • $2 \le W \le 50$
  • $1 \le c_{i, j} \le 10000 \ (1 \le i \le H, 1 \le j \le W) $
  • $c_{1, 1} = c_{H, W} = 0$

入出力例

入力例１

4 5
0 7 1 2 9
1 6 1 4 1
1 1 1 2 10
1 1 3 5 0

出力例１

77

$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4) \to (4, 4) \to (4, 5)$
と移動するのが最適で、総移動距離は $7$、険しさの総和は $11$ である。
したがって $7 \times 11 = 77$ が答えとなる。

入力例２

6 4
0 9 628 244
353 1 3 1933
314 1903 3 1719
10 9 1 2019
3 998 1727 1710
1 4 1 0

出力例２

540

$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to (4, 3) \to $
$ (4, 2) \to (4, 1) \to (5, 1) \to (6, 1) \to (6, 2) \to (6, 3) \to (6, 4)$
と移動するのが最適で、総移動距離は $12$、険しさの総和は $45$ である。
したがって $12 \times 45 = 540$ が答えとなる。
南、東だけでなく西、北にも移動できることに注意しなさい。

入力例３

6 6
0 1070 6139 7774 8935 7172
1630 3739 6325 2416 8866 9808
7985 101 7685 9060 5357 5791
8293 662 8746 4307 8151 9904
7805 2788 4474 8684 3783 3282
8831 6132 7420 4258 9046 0

出力例３

285830