Score : $500$ points

问题描述

存在一个具有 $H$ 行（水平）和 $W$ 列（垂直）的网格。令 $(i, j)$ 表示从上到下的第 $i$ 行、从左到右的第 $j$ 列的方格。

对于每一对整数 $(i, j)$，满足 $1 \leq i \leq H$ 和 $1 \leq j \leq W$，$(i, j)$ 包含一个正整数 $A_{i,j}$。此外，每个方格都被涂成白色。

高桥拥有一块可以覆盖 $h_1$ 行和 $w_1$ 列的矩形黑色印章，而青木则拥有一块可以覆盖 $h_2$ 行和 $w_2$ 列的矩形白色印章。他们将使用这些印章以及这个网格进行一场对抗游戏。

首先，高桥将他的黑色印章压在网格上，涂黑一个包含 $h_1$ 行和 $w_1$ 列的矩形区域。也就是说，他选择一对整数 $(i, j)$，满足 $1 \leq i \leq H - h_1 + 1$ 和 $1 \leq j \leq W - w_1 + 1$，并将所有满足 $i \leq r \leq i + h_1 - 1$ 且 $j \leq c \leq j + w_1 - 1$ 的方格 $(r, c)$ 涂成黑色。

接着，青木将他的白色印章压在网格上，涂白一个包含 $h_2$ 行和 $w_2$ 列的矩形区域。即他选择一对整数 $(i, j)$，满足 $1 \leq i \leq H - h_2 + 1$ 和 $1 \leq j \leq W - w_2 + 1$，并将所有满足 $i \leq r \leq i + h_2 - 1$ 且 $j \leq c \leq j + w_2 - 1$ 的方格 $(r, c)$ 涂成白色。如果其中一些方格已经被高桥涂成了黑色，它们也将变成白色。

游戏的得分定义为在高桥和青木按照上述方式按下印章后，被涂成黑色的方格上所写数字之和。高桥遵循最优策略以使得分尽可能大，而青木遵循最优策略以使得分尽可能小。那么，游戏的得分将会是多少呢？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.
For each pair of integers $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$, $(i, j)$ contains a positive integer $A_{i,j}$. Additionally, every square is painted white.

Takahashi has a rectangular black stamp that can cover $h_1$ rows and $w_1$ columns, and Aoki has a rectangular white stamp that can cover $h_2$ rows and $w_2$ columns. Using these stamps and the grid, they will play a game against each other.

First, Takahashi presses his black stamp to paint a rectangular region with $h_1$ rows and $w_1$ columns black.
That is, he chooses a pair of integers $(i, j)$ such that $1 \leq i \leq H - h_1 + 1$ and $1 \leq j \leq W - w_1 + 1$, and paints black every square $(r, c)$ such that $i \leq r \leq i + h_1 - 1$ and $j \leq c \leq j + w_1 - 1$.

Second, Aoki presses his white stamp to paint a rectangular region with $h_2$ rows and $w_2$ columns white.
That is, he chooses a pair of integers $(i, j)$ such that $1 \leq i \leq H - h_2 + 1$ and $1 \leq j \leq W - w_2 + 1$, and paints white every square $(r, c)$ such that $i \leq r \leq i + h_2 - 1$ and $j \leq c \leq j + w_2 - 1$.
If some of these squares are already painted black by Takahashi, they will also become white.

The game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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}$

Output

Print the game's score when Takahashi follows the optimal strategy to make the score as large as possible and Aoki follows the optimal strategy to make the score as small as possible.

Sample Input 1

3 4 2 3 3 1
3 1 4 1
5 9 2 6
5 3 5 8

Sample Output 1

19

The game will go as follows.

• Initially, all squares are painted white.
• First, Takahashi presses his $2 \times 3$ black stamp to paint the following six squares black: $(2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4)$.
• Second, Aoki presses his $3 \times 1$ white stamp to paint the following three squares white: $(1, 4), (2, 4), (3, 4)$.
• Eventually, the following four squares are painted black: $(2, 2), (2, 3), (3, 2), (3, 3)$, for a score of $9 + 2 + 3 + 5 = 19$.

Sample Input 2

3 4 2 3 3 4
3 1 4 1
5 9 2 6
5 3 5 8

Sample Output 2

0

After Aoki presses his stamp, all squares will be white, for a score of $0$.

Sample Input 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

Sample Output 3

180

update @ 2024/3/10 09:59:49