AT_utpc2021_g Matrix Compressor

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_g あなたは $ H $ 行 $ W $ 列の行列を持っています。行列の $ i $ 行目、$ j $ 列目の成分は $ 1 $ 桁の正整数 $ S_{i,\ j} $ です。 あなたは次の $ 2 $ 種類の操作を好きな順序で、合計 $ H\ +\ W\ -\ 2 $ 回行えます。 - 隣接する $ 2 $ 行 ($ i,\ i\ +\ 1 $ 行目) を選び、$ 2 $ 行の成分の総和の点数を得る。そして、$ 2 $ 行を圧縮する。すなわち、(存在すれば) $ i\ -\ 1 $ 行目以前、$ i $ 行目と $ i\ +\ 1 $ 行目の行ベクトルとしての和、(存在すれば) $ i\ +\ 2 $ 行目以降、をこの順に縦に連結したものに行列全体を置き換える。この操作は、行列が $ 2 $ 行以上である場合に行える。 - 隣接する $ 2 $ 列 ($ j,\ j\ +\ 1 $ 列目) を選び、$ 2 $ 列の成分の総和の点数を得る。そして、$ 2 $ 列を圧縮する。すなわち、(存在すれば) $ j\ -\ 1 $ 列目以前、$ j $ 列目と $ j\ +\ 1 $ 列目の列ベクトルとしての和、(存在すれば) $ j\ +\ 2 $ 列目以降、をこの順に横に連結したものに行列全体を置き換える。この操作は、行列が $ 2 $ 列以上である場合に行える。 獲得可能な合計点数の最大値を求めてください。

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

獲得可能な合計点数の最大値を出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \le\ H,\ W\ \le\ 3000 $ - $ 1\ \le\ S_{i,\ j}\ \le\ 9 $ ### 部分点 - $ 1\ \leq\ H,\ W\ \leq\ 200 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 順に、 $ 2,\ 3 $ 列目、$ 2,\ 3 $ 行目、$ 1,\ 2 $ 行目、$ 1,\ 2 $ 列目、と選ぶのが最適な方法の一つです。このとき、 $ 30\ +\ 28\ +\ 36\ +\ 36\ =\ 130 $ 点が得られます。行列は以下のように変化していきます。 $ $ \\begin{bmatrix} 3\\ &\\ 1\\ &\\ 4\\ \\\\ 1\\ &\\ 5\\ &\\ 9\\ \\\\ 2\\ &\\ 6\\ &\\ 5 \\end{bmatrix} \\to \\begin{bmatrix} 3\\ &\\ 5\\ \\\\ 1\\ &\\ 14\\ \\\\ 2\\ &\\ 11 \\end{bmatrix} \\to \\begin{bmatrix} 3\\ &\\ 5\\ \\\\ 3\\ &\\ 25 \\end{bmatrix} \\to \\begin{bmatrix} 6\\ &\\ 30 \\end{bmatrix} \\to \\begin{bmatrix} 36 \\end{bmatrix} $$