题目描述

一面墙由 $R$ 行 $C$ 列格子组成，初始每格都没有涂料，即涂料层数为 $0$。

工人已经完成 $m$ 次涂刷。每次涂刷选择一个矩形，使其中每个格子的涂料层数增加 $1$，包含矩形边界。

现在必须再进行恰好一次补刷：选择一个连续的 $h$ 行、$w$ 列矩形，使其中每格再增加一层涂料。补刷矩形大小固定，不能旋转，且必须完全位于墙内。

请计算，怎样选择补刷位置，才能让最终涂料层数恰好为 $K$ 的格子最多。只需要输出最多的格子数。

输入格式

第一行六个整数 $R,C,m,K,h,w$。

接下来 $m$ 行，每行四个整数 $x_1,y_1,x_2,y_2$，表示一次已经完成的涂刷，其范围为从第 $x_1$ 行到第 $x_2$ 行、从第 $y_1$ 列到第 $y_2$ 列的所有格子，包含边界。

输出格式

输出一个整数，表示补刷恰好一次后，涂料层数恰好为 $K$ 的最大格子数。

3 4 1 1 1 2
1 1 2 2

6

2 2 1 1 1 2
1 1 2 2

2

样例 1 解释

原来有四格涂料层数为 $1$。可以补刷第 $3$ 行连续两格，使另外两格达到一层，最终有六格符合要求。

样例 2 解释

原来四格都为一层。必须补刷一个 $1\times2$ 矩形，其中两格变为两层，最后只有两格仍符合要求。

数据范围与提示

对于所有测试点：$1\le R,C\le1000$，$1\le m\le200000$，$1\le K\le m+1$，$1\le h\le R$，$1\le w\le C$。

所有已经完成的涂刷满足 $1\le x_1\le x_2\le R$，$1\le y_1\le y_2\le C$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$R,C\le6$，$m\le30$
6—10	$R,C\le50$，$m\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。