印章游戏

题目描述

有一个纵 $H$ 行、横 $W$ 列的方格。从上数第 $i$ 行、从左数第 $j$ 列的格子称为格子 $(i, j)$。

对于每对满足 $1 \le i \le H$ 且 $1 \le j \le W$ 的整数 $(i, j)$，格子 $(i, j)$ 上写有正整数 $A_{i, j}$。此外，所有格子都涂成了白色。

高桥君有一个能覆盖纵 $h_1$ 行、横 $w_1$ 列的矩形黑色印章，青木君有一个能覆盖纵 $h_2$ 行、横 $w_2$ 列的矩形白色印章。

两人用这些印章和方格进行对战游戏。

首先，高桥君使用一次黑色印章，把方格上纵 $h_1$ 行、横 $w_1$ 列的矩形区域涂成黑色。

即，选择一对满足 $1 \le i \le H - h_1 + 1$ 且 $1 \le j \le W - w_1 + 1$ 的整数 $(i, j)$，把满足 $i \le r \le i + h_1 - 1$ 且 $j \le c \le j + w_1 - 1$ 的所有格子 $(r, c)$ 涂成黑色。

接着，青木君使用一次白色印章，把方格上纵 $h_2$ 行、横 $w_2$ 列的矩形区域涂成白色。

即，选择一对满足 $1 \le i \le H - h_2 + 1$ 且 $1 \le j \le W - w_2 + 1$ 的整数 $(i, j)$，把满足 $i \le r \le i + h_2 - 1$ 且 $j \le c \le j + w_2 - 1$ 的所有格子 $(r, c)$ 涂成白色。

此时，如果青木君涂白的格子已经被高桥君涂黑，该格子的颜色会被白色覆盖。

按上述方式高桥君和青木君各使用一次印章后，被涂成黑色的格子上所写整数的总和定义为游戏的“得分”。

高桥君采取使得分尽可能大的最优策略，青木君采取使得分尽可能小的最优策略。请计算游戏的得分是多少。

输入格式

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

$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)$ 这 $6$ 个格子涂成黑色。 接着，青木君用他的纵 $3$ 行、横 $1$ 列的白色印章，把格子 $(1, 4), (2, 4), (3, 4)$ 涂成白色。 最终被涂成黑色的格子是 $(2, 2), (2, 3), (3, 2), (3, 3)$ 这 $4$ 个，因此游戏得分为 $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

数据范围

• $2 \le H, W \le 1000$
• $1 \le h_1, h_2 \le H$
• $1 \le w_1, w_2 \le W$
• $1 \le A_{i, j} \le 10^9$
• 输入均为整数