問題文

あなたは 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 列以上である場合に行える。

獲得可能な合計点数の最大値を求めてください。

制約

• 入力は全て整数
• 1 \le H, W \le 3000
• 1 \le S_{i, j} \le 9

部分点

• 1 \leq H, W \leq 200 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

3 3
314
159
265

出力例 1

130

順に、 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} $$

入力例 2

10 8
82974679
74744362
34499984
86891758
56419363
76176864
78392791
71539599
44588446
71227999

出力例 2

4555