AT_past201912_j 地ならし

给定一个 $h$ 行 $w$ 列的网格图，记第 $i$ 行第 $j$ 列上的数为 $a_{i,j}$。 有一个人，要从左下角的格子出发，到右上角和右下角的格子去。他每一次可以到上下左右相邻的四个格子中已经铺好地砖的格子中去。为了这个目标，他必须在一些网格中铺设地砖，第 $i$ 行第 $j$ 列的网格铺设地砖的成本即为 $a_{i,j}$。铺完地砖的格子可任意移动。 请求出他可能花费的最小成本。

第一行为两个整数 $h$ 和 $w$。 接下来是一个 $h$ 行 $w$ 列的方阵，其中第 $i$ 行第 $j$ 列的数值为 $a_{i,j}$。

输出他所需花费的最小成本。 ### 数据规模与约定 $2 \le h,w \le 50$，$0 \le a_{i,j} \le 100000$，$a_{h,1}=a_{h,w}=a_{1,w}=0$，输入数值均为整数。

### 注意 この問題に対する言及は、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 $ 円のマスをすべて整備するのが最適である。