Problem Description

Giga-kun has bought a computer, started studying programming, joined a company, made money, and finally decided to build a house! The city of Tera is represented by a grid of $H$ rows and $W$ columns. The cell at the $i$-th row and $j$-th column is denoted as $(i, j)$. The land price of cell $(i, j)$ is $A_{i, j}$ yen.

A house can be constructed as follows:

• You can purchase some cells (land) within the city of Tera. The cost to purchase cell $(i, j)$ is $A_{i, j}$ yen. The region of cells purchased must be represented by a single rectangle.
• A house is built on the entire purchased land. If $S$ cells are purchased, the cost to build the house is $S \times K$ yen.

For example, if $K = 5$, the construction shown in (Figure 1) would cost $(1 + 4) + (2 \times 5) = 15$ yen, and the construction shown in (Figure 2) would cost $(6 + 3 + 4 + 1) + (4 \times 5) = 34$ yen. The numbers in the figures represent the land prices of each cell.

Additionally, the land shown in gray in (Figure 3) and (Figure 4) cannot be purchased because the region of purchased land is not represented by a single rectangle.

He currently has $V$ yen and can use his entire fortune to purchase a mansion. He wants to buy the largest possible house. Determine the maximum area of a house he can afford. If it's not possible to purchase a house, output 0. Note that the area of the house is the same as the area of the purchased rectangular region.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Determine the maximum area of a house he can afford. If it's not possible to purchase a house, output 0.

Sample Input and Output

Sample Input #1

1 1 200 500
300

Sample Output #1

1

Sample Input #2

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

Sample Output #2

6

Sample Input #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

Sample Output #3

0

Sample Input #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

Sample Output #4

9

Notes/Hints

Constraints

• $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})$
• All inputs are integers.

Subtasks

This problem is divided into several sub-tasks. Your score for a submission is the sum of the points for the sub-tasks you solved correctly.

1. (11 points) $ H = 1, W = 1 $
2. (17 points) $H = 1, W \leq 20$
3. (28 points) $H \leq 20, W \leq 20$
4. (27 points) $H \leq 75, W \leq 75$
5. (17 points) No additional constraints.

Sample Explanation 1

He can barely afford to purchase the only cell and build a house, costing $ 200 + 300 = 500 $ yen. This example satisfies the constraints of sub-task 1.

Sample Explanation 2

For example, if he purchases the land as shown below:

The cost to purchase the land is $ 10 + 20 + 30 + 40 + 10 + 20 = 130 $ yen, and the cost to build the house is $6 \times 10 = 60$ yen, totaling $ 130 + 60 = 190 $ yen, which is within his budget of $ 200 $ yen. There is no way to purchase a house with an area of 7 or more. This example satisfies the constraints of sub-task 2.

Sample Explanation 3

In this example, it's not possible to purchase a house. Therefore, output 0.

Sample Explanation 4

For example, if he purchases the land as shown below:

The cost to purchase the land and build a house with an area of 9 is $ 235 $ yen, which is just within his budget.

见题面 Input 部分

见题面 Output 部分