SP8951 XIXO - brownie

贝西做了一块矩形的布朗尼蛋糕，可以看作一个 $R \times C$ 的网格，每个小格子里装有一定数量的巧克力豆，记为 $N_{ij}$。其中，$1 \le R, C \le 500$ 且 $0 \le N_{ij} \le 4,000$。 贝西想要把布朗尼切分成 $A \times B$ 块，这样每块都能给一头牛，并且 $1 \le A \le R, 1 \le B \le C$。切分过程需要先在水平面上做 $A-1$ 次切割，将布朗尼分成 $A$ 条横向的部分；然后对每条再各自做 $B-1$ 次垂直切割。这些牛会以贪心的方法抢先挑选出巧克力豆数目最多的区域，剩下巧克力豆最少的区域给贝西。 你的任务是帮助贝西找到一种最优的切割方案，使得她得到的巧克力豆尽可能多。 举个例子，现在有一个 $5$ 行 $\times 4$ 列的布朗尼，巧克力豆的分布如下： ``` 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 ``` 贝西需要把布朗尼切成 $4$ 条，每条再切成两块。她可以选择如下的切割方式： ``` 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 ``` 当其他的牛把他们喜欢的布朗尼块拿走后，贝西依然可以获得 $3$ 颗巧克力豆。

第一行包含四个整数 $R$、$C$、$A$ 和 $B$，分别表示布朗尼的行数、列数以及期望切成的行和列的数量。 接下来有 $R$ 行，每行包含 $C$ 个整数，代表每个小格子里的巧克力豆数。

输出一个整数，表示贝西能通过最优策略获得的最多的巧克力豆数量。

$1 \le R, C \le 500$ $1 \le A \le R$，$1 \le B \le C$ $0 \le N_{ij} \le 4,000$ **本翻译由 AI 自动生成**