问题文

盖千级已经买了电脑，学习了编程，进入公司工作，赚了钱，最后决定建一座房子！

他居住的Terra市由一个 $H$ 行 $W$ 列的网格表示。从上到下的第 $i$ 行，从左到右的第 $j$ 列的格子被表示为 $(i, j)$。此外，格子 $(i, j)$ 的地价是 ¥$A_{i, j}$。

现在，可以按照以下方式建房子：

• 在Terra市的一些格子（土地）上购买。购买 $(i, j)$ 格子需要 ¥$A_{i, j}$。请注意，购买的格子区域必须是一个长方形。
• 在购买的所有土地上建房子。如果购买了 $S$ 个格子，建房子需要花费 ¥$S×K$。

例如，当 $K = 5$ 时，进行如图1所示的建设，费用为 $(1+4)+(2 \\times 5)=15$；进行如图2所示的建设，费用为 $(6+3+4+1)+(4 \\times 5)=34$。图中的数字表示每个格子的地价。

同时，无法购买灰色部分（图3和图4），因为购买的土地区域不是一个长方形。

他目前有 ¥$V$，可以用全部财产来购买豪宅。他想要购买尽可能大面积的房子。

请计算出目前他能购买的最大面积。如果无法购买房子，请输出0。请注意，房子的面积和购买的长方形区域的面积是相同的。

制约条件

• $1 \\leq H, W \\leq 125$
• $1 \\leq A_{i, j}$, $K \\leq 1 \\ 000 \\ 000 \\ 000$
• $1 \\leq V \\leq 1 \\ 000 \\ 000 \\ 000 \\ 000 \\ 000 (=10^{15})$
• 输入都为整数

部分分

该问题分为多个子任务，只有当所有子任务的测试用例都正确时才会被视为“通过此子任务”。提交的源代码得分将是通过的子任务的分数总和。

1. (11 分) $H = 1, W = 1$
2. (17 分) $H = 1, W \\leq 20$
3. (28 分) $H \\leq 20, W \\leq 20$
4. (27 分) $H \\leq 75, W \\leq 75$
5. (17 分) 无额外限制

---

输入

输入以以下格式从标准输入中给出。

$H$ $W$ $K$ $V$ $A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$ $A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$ $:$ $A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$

输出

请计算出他能购买的最大面积作为房子的面积。如果无法购买房子，请输出0。

---

输入示例 1

1 1 200 500
300

输出示例 1

1

只购买了一个格子来建房子，费用为 $200 + 300 = 500$ ，刚好够。该输入满足子任务1的要求。

---

输入示例 2

1 8 10 200
30 40 10 20 30 40 10 20

输出示例 2

6

假设他购买了如下图所示的土地。

在这种情况下，购买土地的费用为 $10 + 20 + 30 + 40 + 10 + 20 = 130$，建房子的费用为 $6 × 10 = 60$，因此总共需要 $130 + 60 = 190$，小于 ¥200，所以可以购买面积为 6 的房子。请注意，无法购买面积大于等于7的房子。该输入满足子任务2的要求。

---

输入示例 3

5 5 10 17
12 19 25 13 25
14 16 18 11 10
19 17 24 26 12
23 11 16 19 14
18 23 27 11 16

输出示例 3

0

在这个输入示例中，无法购买房子，因此输出0。

---

输入示例 4

4 7 10 240
17 12 15 18 19 15 23
22 12 41 16 27 10 10
15 69 18 11 10 23 15
12 20 13 12 17 18 15

输出示例 4

9

例如，如果他购买了如下图所示的土地，并购买了一个面积为9的房子，那么他需要 ¥235，足够了。