题目描述

给你一个 $h \times w$ 的方格, 每个格子上有一个正整数 $a_{i,j}(a_{i,j} \le 10^9)$. A 和 B 在上面玩游戏.

A 先覆盖住一个 $h_1 \times w_1$ 的矩形, B 再覆盖住一个 $h_2 \times w_2$ 的矩形. 定义游戏的得分为所有被 A 覆盖但没有被 B 覆盖的格子上的数的和.

A 想最大化游戏得分, B 想最小化游戏得分, 且他们都会采取最优策略. 求最后的得分.

$h,w \le 1000$, $h_1,h_2 \le h$, $w_1,w_2 \le w$. 得分可能为 $0$.

输入格式

第一行输入六个空格隔开的整数分别为 $h,w,h_1,w_1,h_2,w_2$

接下来输入一个 $h\times w$ 的矩阵 $a$

输出格式

输出一个整数代表答案

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

19

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

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\ \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$

Sample Explanation 1

游戏过程如下

• 一开始，所有的方格都涂成白色。
• 首先，高桥按下他的 $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$ 。

Sample Explanation 2

青木按下印章后，所有方格都将变为白色，得分为 $0$ 。