6185: ABC228 —— F - Stamp Game
[Creator : ]
Description
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?
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?
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}$
$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.
Constraints
$2≤H,W≤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.
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.
Sample 1 Input
3 4 2 3 3 1
3 1 4 1
5 9 2 6
5 3 5 8
Sample 1 Output
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 2 Input
3 4 2 3 3 4
3 1 4 1
5 9 2 6
5 3 5 8
Sample 2 Output
0
After Aoki presses his stamp, all squares will be white, for a score of $0$.
Sample 3 Input
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 3 Output
180