King Jaguar's Pyramid

Time limit1sMemory limit128 MB

Summary

Place an a by b pyramid and an interior c by d chamber on a grid to maximize the sum of base squares minus chamber squares.

Level: Medium6 of 10
Topics: Prefix sum, Brute force, Implementation, Array
Solved: No attempts yet

Problem

After winning a great battle, King Jaguar wants to build a pyramid that will serve both as a monument to his victory and as a tomb for the brave soldiers who died in battle. The pyramid is built on the battlefield and has a rectangular base of $a$ columns by $b$ rows. Inside it, at ground level, is a smaller rectangular chamber of $c$ columns by $d$ rows that holds the corpses and weapons of the fallen soldiers.

The King's architects have surveyed the battlefield as an $m$ columns by $n$ rows grid and have measured the elevation of each square as an integer.

Both the pyramid and the chamber must be built covering complete squares of the grid, with their sides parallel to those of the battlefield. The elevations of the squares of the internal chamber stay unchanged, but the remaining terrain of the base is leveled by moving sand from higher squares to lower ones. The final elevation of the base is the average elevation of all base squares excluding those of the chamber. The architects may place the chamber anywhere inside the pyramid as long as a wall at least one square thick surrounds the chamber on all sides.

The figure shows an example battlefield; the number in each square is the elevation of the terrain at that position. The gray squares are the base of the pyramid, and the enclosed white squares are the chamber. The figure illustrates one optimal placement.

Given the dimensions of the field, the pyramid, and the chamber, place the pyramid on the field and the chamber inside the pyramid so that the final elevation of the base is as large as possible, and report that outcome.

Input

The first line contains six space-separated integers: $m$ , $n$ , $a$ , $b$ , $c$ , and $d$ .

Each of the next $n$ lines contains $m$ space-separated integers giving the elevations of one row of the grid. The first of these lines is the top row (row 1) and the last is the bottom row (row $n$ ); the $m$ integers in each line are the elevations of that row's squares starting from column 1.

Output

Print a single integer: the value achieved by a placement that maximizes the final elevation.

The number of leveled base squares is always fixed at $a\cdot b - c\cdot d$ , and the final (average) elevation equals $\dfrac{S}{a\cdot b - c\cdot d}$ , where $S$ is the sum of the elevations of all base squares minus the sum of the elevations of the chamber squares. Because the denominator is fixed, maximizing the average is equivalent to maximizing $S$ . Therefore, output the maximum value of $S$ over all valid placements.

Constraints

$3 \le m \le 1000$
$3 \le n \le 1000$
$3 \le a \le m$
$3 \le b \le n$
$1 \le c \le a - 2$
$1 \le d \le b - 2$
All elevations are integers from $1$ to $100$ .

Examples3

Example 1

Input

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

Expected output

Example 2
Input
```
3 3 3 3 1 1
1 2 3
4 100 6
7 8 9
```
Expected output
```
40
```

Example 3

Input

4 4 3 3 1 1
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5

Expected output