AT_abc228_f [ABC228F] Stamp Game

有一个高 $H$ 行、宽 $W$ 列的网格。第 $i$ 行第 $j$ 列的格子记作格子 $(i, j)$。 对于所有满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$，格子 $(i, j)$ 上写有正整数 $A_{i, j}$。此外，所有格子初始都被涂成白色。 高桥君有一个高 $h_1$ 行、宽 $w_1$ 列的黑色矩形印章，青木君有一个高 $h_2$ 行、宽 $w_2$ 列的白色矩形印章。 两人将用这些印章和网格进行对战游戏。 首先，高桥君用他的黑色印章在网格上选择一个高 $h_1$ 行、宽 $w_1$ 列的矩形区域，将该区域内的所有格子涂成黑色。 也就是说，他选择一个满足 $1 \leq i \leq H - h_1 + 1$ 且 $1 \leq j \leq W - w_1 + 1$ 的整数对 $(i, j)$，然后将所有满足 $i \leq r \leq i + h_1 - 1$ 且 $j \leq c \leq j + w_1 - 1$ 的格子 $(r, c)$ 涂成黑色。 接着，青木君用他的白色印章在网格上选择一个高 $h_2$ 行、宽 $w_2$ 列的矩形区域，将该区域内的所有格子涂成白色。 也就是说，他选择一个满足 $1 \leq i \leq H - h_2 + 1$ 且 $1 \leq j \leq W - w_2 + 1$ 的整数对 $(i, j)$，然后将所有满足 $i \leq r \leq i + h_2 - 1$ 且 $j \leq c \leq j + w_2 - 1$ 的格子 $(r, c)$ 涂成白色。 此时，如果青木君要涂白的格子已经被高桥君涂黑，则这些格子会被白色覆盖，最终颜色为白色。 如上所述，高桥君和青木君各用一次印章后，所有被涂成黑色的格子上所写整数的总和即为本次游戏的“得分”。高桥君会采取使得分尽可能大的最优策略，青木君会采取使得分尽可能小的最优策略。请你求出最终的游戏得分。

输入按以下格式从标准输入给出。 > $H$ $W$ $h_1$ $w_1$ $h_2$ $w_2$ > $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ > $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ > $\vdots$ > $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

输出在双方都采取最优策略时，游戏的最终得分。

## 限制条件 - $2 \leq H, W \leq 1000$ - $1 \leq h_1, h_2 \leq H$ - $1 \leq w_1, w_2 \leq W$ - $1 \leq A_{i, j} \leq 10^9$ - 输入均为整数 ## 样例解释 1 游戏过程如下： - 开始时，所有格子都是白色。 - 首先，高桥君用 $2$ 行 $3$ 列的黑色印章，将格子 $(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)$ 共 $6$ 个格子涂成黑色。 - 然后，青木君用 $3$ 行 $1$ 列的白色印章，将格子 $(1, 4), (2, 4), (3, 4)$ 涂成白色。 - 最终被涂成黑色的格子为 $(2, 2), (2, 3), (3, 2), (3, 3)$ 共 $4$ 个，因此游戏得分为 $9 + 2 + 3 + 5 = 19$。 ## 样例解释 2 青木君用印章后，所有格子都变成白色，游戏得分为 $0$。 由 ChatGPT 4.1 翻译