Pirate's Treasure Division

Pirates in the Caribbean are famous for their peculiar treasure‐dividing ceremony. After a raid, the pirates place their precious jewels into terra cotta cubes of side length 1. Each cube has a number v marked on its lid representing the jewel's value. These cubes are arranged in a rectangular grid with l columns and w rows. The box in the i-th row and j-th column has value \(v_{i,j}\) (with the left‐bottom box as row 1, column 1).

When it is a pirate's turn to pick treasures, he is given a wooden box with a base of size \(m\times n\) and height \(h\) (its height is irrelevant in this problem). He is required to use the wooden box to collect a contiguous block (submatrix) of terra cotta boxes exactly matching the base of the wooden box. The wooden box is oriented so that its side of length \(m\) is parallel to the grid's side of length \(w\). After a selection, the chosen terra cotta boxes are immediately replaced by empty boxes (value 0).

The selection is done in batches. Let the bottom‐left (minimal) cell of the submatrix chosen in the k-th batch be at position \((i_k, j_k)\). The following rules must be satisfied for a selection to be valid:

• The entire submatrix of size \(m\times n\) starting at \((i_k, j_k)\) must lie within the grid.
• The chosen starting position must satisfy \[ \left\lfloor \frac{m}{2} + j_k - \frac{w}{2} \right\rfloor \le a, \] where \(a\) is a given integer.
• For \(k \ge 2\):
  • If \(j_k = j_{k-1}\), then \(i_k - i_{k-1} \ge d_1\).
  • If \(j_k \neq j_{k-1}\), then \(i_k - i_{k-1} \ge d_2\).

You are given the grid values and a sequence of \(Q\) proposed selections. Process the selections in order. For each selection, if it is valid according to the rules above, add the sum of the values in the selected submatrix to a total and set those cells to 0 (so they cannot contribute in later selections). If a selection is invalid, ignore it. Finally, output the total collected sum.

Note: For the purpose of the ordering rules (the \(d_1\) and \(d_2\) constraints), only the last valid selection is considered.

inputFormat

The input is given as follows:

w l m n a Q
v1,1 v1,2 ... v1,l
v2,1 v2,2 ... v2,l
...
vw,1 vw,2 ... vw,l
 i1 j1
 i2 j2
 ...
 iQ jQ
 d1 d2

The grid is given in bottom-to-top order (i.e. row 1 is the bottom row). Each of the following Q lines represents a proposed selection with \(i\) and \(j\) indicating the bottom‐left cell of the submatrix.

\(d_1\) and \(d_2\) are the minimum differences required in the i-coordinate between consecutive valid selections, depending on whether the \(j\)-coordinate is the same or not.

outputFormat

Output a single integer, the total collected sum after processing all selections.

sample

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

18