Zombies vs Plants: Energy Optimization

In this problem, we consider a modified version of the classic Plants vs Zombies game. The game is played on an N×M grid (with rows numbered from 0 to N-1 and columns from 0 to M-1). There is exactly one plant in each cell. We denote the plant at row r and column c by \(P_{r,c}\).

Each plant \(P_{r,c}\) is described by two functions:

• \(\operatorname{Score}(P_{r,c})\): when a zombie destroys \(P_{r,c}\), it gains energy equal to \(\operatorname{Score}(P_{r,c})\) if this value is nonnegative, or it must pay \(-\operatorname{Score}(P_{r,c})\) energy if the score is negative.
• \(\operatorname{Attack}(P_{r,c})\): a set of grid positions that this plant protects. Note: For each plant, its own cell (r, c) is not included in its attack set.

Zombies attack by entering a row from the right edge. In any given row r, the zombie must attack plants in order starting from \(P_{r,M-1}\) (the right‐most plant), then \(P_{r,M-2}\), and so on. In other words, if you want to attack plant \(P_{r,c}\) with \(0 \le c c\) in that row.

However, the plants can defend themselves. Their attack power is infinite: if a zombie enters any position that lies in the attack set of a surviving (i.e. not yet attacked) plant, the zombie is instantly eliminated (and it does not get the chance to attack the plant at that position). This means that if the zombie is traversing a row in order to attack a plant, every cell that the zombie travels through must not be under the protection of any surviving plant (from any row).

The zombies can choose the order in which they attack plants. For each row r, let \(X_r\) be the number of plants (from the right) to attack. That is, if \(X_r = k>0\), then the attacked plants in row r are \(P_{r,M-k}, P_{r,M-k+1}, \dots, P_{r,M-1}\); all other plants in that row remain. If \(X_r=0\), no plant in row r is attacked and hence no zombie will traverse that row.

Now consider an attack relation: if a plant \(P_{u,v}\) defends position \((r,j)\) (denoted by an attack relation \((u,v)\to(r,j)\)), then whenever row r is attacked (i.e. \(X_r>0\)) and the zombie passes through a cell \((r,j)\) (which happens if \(j \ge M - X_r\)), the zombie will be eliminated UNLESS plant \(P_{u,v}\) has already been attacked. In our selection, attacking \(P_{u,v}\) means that the column \(v\) is among the attacked plants in row \(u\), i.e. \(v \ge M-X_u\). Thus, each attack relation \((u,v)\to (r,j)\) imposes the following constraint:

[ \text{If } X_r>0 \text{ and } j \ge M-X_r, \text{ then we must have } X_u \ge M-v. ]

Your task is to choose \(X_r\) (for each row \(r = 0,1,\dots,N-1\)) so as to maximize the total energy gained from the attacked plants while satisfying all the constraints imposed by the surviving plants’ attack ranges.

The total energy gained is computed as:

[ \text{Total Energy} = \sum_{r=0}^{N-1} \sum_{c=M-X_r}^{M-1} \operatorname{Score}(P_{r,c]). ]

</p>

Find the maximum total energy that the zombies can obtain.

inputFormat

The input is given as follows:

1. The first line contains two integers N and M (the number of rows and columns).
2. The next N lines each contain M integers. The c-th integer in the r-th line represents \(\operatorname{Score}(P_{r,c})\).
3. The next line contains a single integer T, representing the total number of attack relations.
4. Each of the following T lines contains four integers: u, v, r, and j, meaning that plant \(P_{u,v}\) defends the grid position \((r,j)\). It is guaranteed that \((r,j)\) is different from \((u,v)\).

outputFormat

Output a single integer, the maximum total energy the zombies can obtain by choosing an attack scheme that satisfies all the conditions.

sample

2 3
1 -2 3
-4 5 2
2
0 1 1 2
1 2 0 2

6