P3017 [USACO11MAR] Brownie Slicing G

Bessie 烤了一个长方形的布朗尼，可以看作是一个 $R \times C$ 的网格（$1 \le R \le 500$；$1 \le C \le 500$），由小方块组成。在第 $i$ 行，第 $j$ 列的方块中有 $N_{ij}$（$0 \le N_{ij} \le 4,000$）颗巧克力豆。 Bessie 想把布朗尼分成 $A \times B$ 块（$1 \le A \le R$；$1 \le B \le C$）：每头牛一块。布朗尼的切割方式是先进行 $A-1$ 次水平切割（总是在整数坐标上），将布朗尼分成 $A$ 条带。然后每条带独立地进行 $B-1$ 次垂直切割，也是在整数边界上。其他 $A \times B - 1$ 头牛各自选择一块布朗尼，剩下最后一块给 Bessie。由于它们很贪心，它们会把巧克力豆最少的一块留给 Bessie。 假设 Bessie 以最优方式切割布朗尼，求 Bessie 能获得的最多巧克力豆数。 例如，考虑一个 5 行 4 列的布朗尼，巧克力豆分布如下： ``` 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 ``` Bessie 必须将布朗尼分成 4 条水平带，每条带有两块。Bessie 可以这样切割布朗尼： ``` 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 ``` 因此，当其他贪心的牛选择它们的布朗尼块时，Bessie 仍然可以得到 3 颗巧克力豆。

\* 第 1 行：四个用空格分隔的整数：$R$，$C$，$A$ 和 $B$ \* 第 2 行到第 $R+1$ 行：第 $i+1$ 行包含 $C$ 个用空格分隔的整数：$N_{i1}, ..., N_{iC}$

\* 第 1 行：一个整数：Bessie 在她的布朗尼上能保证获得的最多巧克力豆数

（由 ChatGPT 4o 翻译）