Enclosing Beans Game

Are you tired of playing the traditional dot-eating game on your phone? Now, MOKIA has introduced a new "Enclosing Beans Game". In this game, you are given an N×M grid with D beans, each having a score value V_i. Some cells in the grid may also contain obstacles.

The rules are very simple:

1. You may choose any cell as the starting cell.
2. You then move step by step to one of the four adjacent cells (up, down, left, right) until you return to the starting cell. The path you take will form a closed polygon (which may be self‑intersecting).
3. Your final score is defined as the sum of the scores of all beans that are enclosed (strictly inside) by the polygon, minus the total number of moves you made.
4. At any moment you are not allowed to move into a cell that contains an obstacle or a bean. (Beans and obstacles are static; beans are only "collected" if they lie strictly inside the enclosing path.)
5. You may choose to do nothing, earning a score of 0, which is the minimum possible score.

Note on enclosure: A bean is considered enclosed if its center lies in the interior of the polygon formed by your path. For example, a rectangular path that surrounds a bean will count it, whereas a path that touches the 8 neighbors around a bean but does not enclose its center will not count.

Help Bubu, who just can’t seem to get a high score by himself, by writing a program that outputs the maximum achievable score using any valid cycle on the grid.

Hint: Although a valid cycle can have any shape, one may restrict attention to rectangular cycles with edges parallel to the grid axes. For a rectangle defined by top‑left cell (r₁, c₁) and bottom‑right cell (r₂, c₂) (with r₂ − r₁ ≥ 2 and c₂ − c₁ ≥ 2 so that the area is non‐empty), the border cells (through which you travel) must be empty. The beans that lie strictly inside (i.e. with row index between r₁ and r₂ and column index between c₁ and c₂) contribute to your score. The cost of the cycle is the number of moves, which for a rectangle is exactly 2((r₂−r₁)+(c₂−c₁)). Thus the score is given by:

$$\text{score}=\sum_{(i,j)\in \text{interior}}V_{i,j} - 2((r_2-r_1)+(c_2-c_1))$$

Your task is to compute the maximum achievable score, where you may also choose to do nothing and get 0.

inputFormat

The input is given as follows:

N M
D
r1 c1 V1
r2 c2 V2
... (D lines in total)
O
r1 c1
r2 c2
... (O lines in total)

Where:

• N and M (1-indexed) denote the number of rows and columns of the grid.
• D is the number of beans. Each of the following D lines contains three integers: row index, column index, and the bean's score V_i.
• O is the number of obstacles. Each of the next O lines contains two integers denoting the row and column of an obstacle.
• It is guaranteed that beans and obstacles do not share the same cell.

outputFormat

Output a single integer, the maximum achievable score. If no valid cycle produces a positive score, output 0.

sample

4 4
1
2 2 10
0

2