Description

It is said that after each raid, if there are valuables such as gold, silver, and jewels, the Caribbean pirates divide the loot with a special ceremony.

They first pack the jewels into earthenware cubes with side length $1$, and mark the value $v$ of the jewels on the lid. Then they arrange these boxes into a rectangle of length $l$ and width $w$ (if the jewels are not enough, empty earthenware boxes may be used to fill the empty positions and are marked with value $0$). The value marked on the box at row $i$ and column $j$ is $v_{i,j}$ (where $0 < i \leq l$, $0 < j \leq w$; the box at the lower-left corner is at row $1$, column $1$).

According to their contributions, the pirates decide an order for picking treasures. The pirate whose turn it is will be given a wooden crate with a base of $m \times n$ and height $h$, and is required to fill the crate with the selected earthenware boxes, then close the crate lid.

The boxes must be selected in batches. Each batch must be a contiguous rectangular region equal to the crate’s base, and the side of the crate of length $m$ must be parallel to the side of the arranged rectangle that has length $w$. The positions of the selected boxes are immediately filled with empty boxes after removal. The pirate starts from the exact center of the bottom edge of the arranged rectangle, i.e., from the lower-right corner of the box at row $1$ and column $\lfloor \frac{w}{2} \rfloor$, and proceeds upward along the vertical line that is the left edge of column $\lfloor \frac{w}{2} \rfloor$ of the arranged rectangle.

As shown by the bold arrows in the figure. Let the lower-left corner of the $k$-th selected region be the box at row $i_k$, column $j_k$. The index $j_k$ must satisfy $\lfloor \frac{m}{2} + j_k - \frac{w}{2} \rfloor \leq a$, where $k \geq 1$. Moreover, when $j_k = j_{k-1}$, $i_k$ must satisfy $i_k - i_{k-1} \geq d_1$; when $j_k \neq j_{k-1}$, $i_k$ must satisfy $i_k - i_{k-1} \geq d_2$, where $k \geq 2$.

Input Format

The first line contains eight positive integers separated by single spaces: $l, w, m, n, h, a, d_1, d_2$. From the second line to line $l + 1$, each line contains $w$ integers. Denote the integer in row $i + 1$, column $j$ by $v_{i,j}$ ($1 \leq j \leq w$, $1 \leq i \leq l$), representing the jewel value marked on the box lid. The integers on the same line are separated by single spaces.

Note: In the input, $v_{i,j}$ starts from the top-left box, but for the problem definition the box at the lower-left corner is at row $1$, column $1$.

Output Format

Output a single integer on the first line: the maximum total jewel value $T$ that can be obtained.

10 12 3 2 3 5 2 3
0 0 0 1 0 1 1 1 9 1 1 1
1 1 2 1 1 1 0 0 8 2 1 8
1 0 1 0 1 6 1 1 0 0 1 1
1 1 2 1 2 1 1 1 3 1 1 1
0 1 0 1 1 1 2 1 6 0 2 1
1 1 0 1 0 1 1 2 1 1 1 0
1 0 1 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 9 0 0 1 1 1
0 0 1 0 1 2 1 9 1 1 0 1
0 1 1 1 1 1 9 1 1 1 1 1

59

Hint

$d_1, d_2 \geq n$, $1 \leq l, w, a, d_1, d_2 \leq 2 \times 10^3$, $1 \leq m, n \leq 200$, $1 \leq h \leq 20$, $0 \leq v_{i,j} \leq 255$.

Translated by ChatGPT 5