Description

To enhance the park’s scenery, we need to build a flowerbed in the park and, around the flowerbed, construct a green belt so that the flowerbed is enclosed by the green belt.

If we regard the park as an $M\times N$ rectangle, then the flowerbed can be regarded as a $C\times D$ rectangle, and the green belt together with the flowerbed can be regarded as an $A\times B$ rectangle.

If we define the fertility of a rectangular land region as the sum of the fertility values of all unit cells within that region, then the fertility of the green belt equals the fertility of the $A\times B$ block minus the fertility of the $C\times D$ block.

To make the green belt grow vigorously, we want the fertility of the green belt to be maximized.

Input Format

The first line contains six positive integers $M,N,A,B,C,D$.

Then follows an $M\times N$ numeric matrix. The element in row $i$ and column $j$ is an integer $x_{i,j}$, representing the fertility of the land at row $i$ and column $j$ of the park.

Output Format

Output a single positive integer, the maximum fertility of the green belt.

4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

132

Hint

For $30\%$ of the testdata, $1\leq M,N\leq 50$.

For $100\%$ of the testdata, $1\leq M,N\leq 1000$, $1\leq A\leq M$, $1\leq B\leq N$, $1\leq C\leq A-2$, $1\leq D\leq B-2$, $1\leq x_{i,j}\leq 100$.

Translated by ChatGPT 5