102285: [AtCoder]ABC228 F - Stamp Game

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

问题描述

有一个包含$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)$涂成白色。 如果这些方格中的一些已经被高桥涂成黑色，它们也会变成白色。

游戏的得分定义为在高桥和相贺按下他们的印章后，涂成黑色的方格上所写的整数之和。 高桥遵循最佳策略，使得分尽可能大，而相贺遵循最佳策略，使得分尽可能小。 游戏的得分会是多少呢？

约束条件

• $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$
• 输入中的所有值都是整数。

输入

输入通过标准输入按以下格式给出：

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

输出

当高桥遵循最佳策略使得分尽可能大，而相贺遵循最佳策略使得分尽可能小时，打印游戏的得分。

样例输入 1

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

样例输出 1

19

游戏将会如下进行。

• 最初，所有方格都被涂成白色。
• 首先，高桥按下他的$2 \times 3$黑色印章，将以下六个方格涂成黑色：$(2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4)$。
• 其次，相贺按下他的$3 \times 1$白色印章，将以下三个方格涂成白色：$(1, 4), (2, 4), (3, 4)$。
• 最终，以下四个方格被涂成黑色：$(2, 2), (2, 3), (3, 2), (3, 3)$，得分是$9 + 2 + 3 + 5 = 19$。

样例输入 2

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

样例输出 2

0

在相贺按下他的印章后，所有方格都会被涂成白色，得分为$0$。

样例输入 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

样例输出 3

180