AT_utpc2021_g.Matrix Compressor

你有一个 $ H $ 行 $ W $ 列的矩阵，每个矩阵元素都是 $ 1 $ 到 $ 9 $ 之间的正整数，即 $ S_{i, j} $。

你可以按照任意顺序执行以下两种操作，总共可以进行 $ H + W - 2 $ 次：

1. 行操作：选择两行相邻的行（第 $ i $ 行和第 $ i + 1 $ 行），获得这两行所有元素之和作为得分，然后将这两行压缩。具体操作是：用（如果有）第 $ i - 1 $ 行及之前的行、第 $ i $ 行和第 $ i + 1 $ 行的所有元素之和、（如果有）第 $ i + 2 $ 行及之后的行，按照这个顺序重新组成矩阵。此操作要求矩阵至少有两行。

2. 列操作：选择两列相邻的列（第 $ j $ 列和第 $ j + 1 $ 列），获得这两列所有元素之和作为得分，然后将这两列合并。具体操作是：用（如果有）第 $ j - 1 $ 列及之前的列、第 $ j $ 列和第 $ j + 1 $ 列的元素之和、（如果有）第 $ j + 2 $ 列及之后的列，按照这个顺序重新组成矩阵。此操作要求矩阵至少有两列。

请计算通过上述操作可以获得的最大总分数。

输入由标准输入给出，格式如下：

$ H $ $ W $
在接下来的 $ H $ 行中，每行输入 $ W $ 个整数，表示矩阵的元素。

输出可以获得的最大总分数。

• 所有输入均为整数
• $ 1 \le H, W \le 3000 $
• $ 1 \le S_{i, j} \le 9 $

部分分数

• 对于满足 $ 1 \le H, W \le 200 $ 的测试用例，若答案正确则可以得到 $ 30 $ 分。

示例说明

例如，按顺序选择第 $ 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}$$

本翻译由 AI 自动生成