AT_s8pc_3_d お土産購入計画2

[problemUrl]: https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_d E869120とsquare1001は, $ H\ \times\ W $ のマス目を移動して, お土産を買うことにしました。 左上のマスがスタート地点, 右下のマスがゴール地点です。 上から$ i $番目, 左から$ j $番目には, $ a_{i,\ j} $ 個のお土産が売られています。 そこで, 2人で協力してお土産をできるだけ多く集めることにしました。 しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。 そのとき, 買うことができるお土産の個数の最大値を求めなさい。

入力は以下の形式で標準入力から与えられる。 > $ H\ W $ $ a_{1,\ 1}\ a_{1,\ 2}\ \cdots\ a_{1,\ W} $ $ a_{2,\ 1}\ a_{2,\ 2}\ \cdots\ a_{2,\ W} $ $ \vdots\ \vdots\ \vdots $ $ a_{H,\ 1}\ a_{H,\ 2}\ \cdots\ a_{H,\ W} $ - $ 1 $行目に, 整数$ H $と$ W $が与えられる。 - $ 2 $行目から$ H+1 $行目には, $ W $個の整数が空白区切りで与えられる。

出力は以下の形式で標準出力に従うこと。 - 買うことのできるお土産の個数の最大値を1行に出力しなさい。

### 制約 - $ 1\ \le\ H,\ W\ \le\ 200 $ - $ 0\ \le\ a_{i,\ j}\ \le\ 10^5 $ ### 小課題 小課題1 \[50点\] - $ 1\ \le\ H\ \le\ 2 $ を満たす。 小課題2 \[80点\] - $ 1\ \le\ H\ \le\ 3 $ を満たす。 小課題3 \[120点\] - $ 1\ \le\ H,\ W\ \le\ 7 $ を満たす。 小課題4 \[150点\] - $ 1\ \le\ H,\ W\ \le\ 30 $ を満たす。 小課題5 \[200点\] - 追加の制約はない。 ### Sample Explanation 1 ここでは, 上から $ i $ 番目, 左から $ j $ 番目を $ (i,\ j) $ とします。 そのとき, 次のような進み方が最適です。 - E869120は, $ (1,\ 1)\ -\ >\ (1,\ 2)\ -\ >\ (1,\ 3)\ -\ >\ (2,\ 3)\ -\ >\ (3,\ 3) $ と進む。 - square1001は, $ (1,\ 1)\ -\ >\ (2,\ 1)\ -\ >\ (3,\ 1)\ -\ >\ (3,\ 2)\ -\ >\ (3,\ 3) $ と進む。 また, 2人は合計で21個のお土産を買うことができます。