AT_past201912_j 地ならし

[problemUrl]: https://atcoder.jp/contests/past201912-open/tasks/past201912_j 縦 $ H $ マス、横 $ W $ マスの合計 $ H\ \times\ W $ 個の正方形のマスに区切られた区画がある。左下隅、右下隅、右上隅の $ 3 $ マスを除いてこれらのマスはすべて未整備で、上から $ i $ 行目、左から $ j $ 列目 $ (1\ \leqq\ i\ \leqq\ H,\ 1\ \leqq\ j\ \leqq\ W) $ のマスを整備するのに必要な費用は $ A_{i,j} $ 円である。 区画の左下隅のマスに物体が置かれている。あなたは、これをまず右下隅のマスまで移動させ、次に右上隅のマスまで移動させようとしている。 物体の移動は、物体が現在占有するマスから上下左右に隣接するマスに動かすことを繰り返して行う。このとき、物体が通るマスはすべて整備されている必要がある。一度整備を行ったマスの上は何度でも物体を通すことができる。 このとき、マスの整備に必要な最小の合計費用を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A_{1,1} $ $ A_{1,2} $ $ \ldots $ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $ \ldots $ $ A_{2,W} $ $ : $ $ A_{H,1} $ $ A_{H,2} $ $ \ldots $ $ A_{H,W} $

必要な最小の合計費用を表す整数を出力せよ。

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leqq\ H,\ W\ \leqq\ 50 $ - $ 0\ \leqq\ A_{i,j}\ \leqq\ 100,000 $ - $ A_{H,1}\ =\ A_{H,W}\ =\ A_{1,W}\ =\ 0 $ - 入力中の値はすべて整数である。 ### Sample Explanation 1 整備費用が $ 1 $ 円のマスをすべて整備するのが最適である。