F - Stamp Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

縦 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 列の長方形の白いスタンプを持っています。
2 人はこれらのスタンプとマス目を使って対戦ゲームをします。

まず高橋君が、持っている黒いスタンプを 1 回使って、マス目の縦 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) を黒色に塗りつぶします。

次に青木君が、持っている白いスタンプを 1 回使って、マス目の縦 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) を白色に塗りつぶします。
このとき、青木君が白色に塗るマスがすでに高橋君によって黒色に塗られていた場合は、そのマスの色は白で上書きされます。

上記の通りに高橋君と青木君がスタンプを 1 回ずつ使った後の、黒色に塗られたマスに書かれた整数の合計を、ゲームの「スコア」とします。 高橋君はスコアが出来るだけ大きくなるように、青木君はスコアが出来るだけ小さくなるように、それぞれ最適な戦略をとります。 ゲームのスコアがいくらになるかを求めて下さい。

制約

  • 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 行横 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

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

Score : 500 points

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