P2219 [HAOI2007] Building the Green Belt

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.

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 a single positive integer, the maximum fertility of the green belt.

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