配点 : {100} 点
問題文
你 H 行 W 拥有行列的矩阵。矩阵的 i 行目、j 第 n 列的元素是 1 带数字的正整数 我决定计算 S_{i, j} 。
你可以进行以下 2 种操作,按照任意顺序,总共进行 H + W - 2 次。
- 相邻 2 行 (i, i + 1 选择第 n 行)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 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
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
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