当前没有测试数据。

F - 圖章遊戲

分數：500

問題描述

有一個由H行和W列組成的網格。 對於每對整數(i, j)（1 ≤ i ≤ H，1 ≤ j ≤ W），(i, j)處都有一個正整數A_i,j。此外，每個方格都塗成了白色。

高橋有一個可以覆蓋h₁行w₁列的黑色圖章，青木有一個可以覆蓋h₂行w₂列的白色圖章。 他們將使用這些圖章和網格進行一場對戰。

首先，高橋將他的黑色圖章按下，將一個由h₁行w₁列圖案的區域塗成黑色。 換句話說，他選擇一對整數(i, j)（1 ≤ i ≤ H - h₁ + 1，1 ≤ j ≤ W - w₁ + 1），並將該區域中的每個方格(r, c)塗成黑色，其中i ≤ r ≤ i + h₁ - 1且j ≤ c ≤ j + w₁ - 1。

其次，青木按下他的白色圖章，將一個由h₂行w₂列圖案的區域塗成白色。 換句話說，他選擇一對整數(i, j)（1 ≤ i ≤ H - h₂ + 1，1 ≤ j ≤ W - w₂ + 1），並將該區域中的每個方格(r, c)塗成白色，其中i ≤ r ≤ i + h₂ - 1且j ≤ c ≤ j + w₂ - 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}$

輸出

當高橋使用最優策略使得分數最大，青木使用最優策略使得分數最小時，輸出遊戲的分數。

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

19

遊戲的進行如下：

• 首先，所有方格都被塗成白色。
• 接著，高橋使用2行3列的黑色圖章將以下六個方格塗成黑色：(2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4)。
• 然後，青木使用3行1列的白色圖章將以下三個方格塗成白色：(1, 4), (2, 4), (3, 4)。
• 最後，以下四個方格被塗成黑色：(2, 2), (2, 3), (3, 2), (3, 3)，分數為9 + 2 + 3 + 5 = 19。

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

0

青木按下圖章後，所有方格都變成了白色，分數為0。

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

180