问题描述

有一个 $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