Problem Description

Pirate Dick has grown tired of fighting, marauding, theft, and causing misery for many on the open seas. Therefore, he decided to retire and found a perfect island to spend the rest of his days, as long as he does not run out of gold coins. He now has a large amount of gold coins and wants to store them in a chest (after all, he is a pirate). Dick can construct a rectangular chest with integer dimensions, where the top dimensions can be up to a specified maximum size, but the height can be any integer. Now, he needs a place to hide this chest. While exploring the island, he found a perfect solution.

Dick will hide his chest by submerging it in a murky pond. The pond has a rectangular surface and completely fills the bottom of a valley with high vertical rocky walls. Dick has surveyed the pond and knows the depth of each square in a Cartesian coordinate grid system placed on the pond surface. When Dick submerges the chest, it will sink as far as possible until it touches the bottom. The top of the chest will remain parallel to the pond’s surface, and the chest will be aligned with the grid squares. The water displaced by the submerged chest will raise the level of the pond’s surface (this will occur even if there is no space around the chest for the displaced water to rise). The walls of the valley are high enough that the water can never splash out of the valley. Of course, since the chest must be invisible, its top must be strictly below the surface of the pond. Your task is to find the volume of the largest chest that Pirate Dick can hide this way.

In Figure I.1, the leftmost image shows a pond, the middle image shows a possible placement of a chest with a volume of 3, and the rightmost image shows a placement of a chest with a volume of 4, which is the maximum possible volume. Note that if the second chest were made one unit taller, its top would be visible because it would be at exactly the same height as the surface of the water.

Input Format

The input consists of a single test case. A test case starts with a line containing four integers \(a, b, m,\) and \(n (1 \leq a, b, m, n \leq 500)\). The pond’s surface dimensions are \(m \times n\) and the maximum size of the top (and bottom) of the chest is \(a \times b\). Additionally, \(a\) and \(b\) are small enough that it is not possible to cover the entire pond with a chest with top size \(a \times b\). Each of the remaining \(m\) lines in the test case contains \(n\) integers \(d_{i,j}\) specifying the pond’s depth at grid square \((i, j)\), where \(0 \leq d_{i,j} \leq 10^9\) for each \(1 \leq i \leq m\) and \(1 \leq j \leq n\).

Output Format

Display the maximum volume of a rectangular chest with integer dimensions (where one of the dimensions of the top is bounded by \(a\) and the other is bounded by \(b\)) that can be completely submerged below the surface of the pond. If no chest can be hidden in the pond, display \(0\).

Sample Input and Output

Input Sample #1

3 1 2 3
2 1 1
2 2 1

Output Sample #1

4

Input Sample #2

4 1 1 5
2 0 2 2 2

Output Sample #2

12

Input Sample #3

2 3 3 5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2

Output Sample #3

18

见题面 Input 部分

见题面 Output 部分