Mineral Extraction

A project is underway to develop a planet in a neighboring star system. Several batches of robots will be sent to the planet to mine minerals.

The mining area is a grid rectangle of size $w$ by $h$, with cells from $(1, 1)$ to $(w, h)$. Some cells contain specialist bases, and robot batches are delivered to these bases. There are $s$ bases in total, and the $i$-th base is in the cell $(x_i, y_i)$.

The $j$-th batch is delivered to base $b_j$ and contains $n_j$ robots. Each robot in the batch has mobility $m_j$. Once a batch arrives at its base, each robot moves across the surface from the base to some cell. A robot with mobility $m$ may move at most $m$ times, each time to one of the eight neighboring cells (see Fig. 1).

After the robots from all delivered batches are placed, they are activated and start mining. During movement, any number of robots may share a cell. However, after activation, no cell may hold more than $q$ robots.

The management has information about $t$ batches that can be sent to the planet in sequence. After all batches are delivered, limited mobility may make it impossible to place the robots so that no cell holds more than $q$ of them. Therefore management chooses the first $k$ batches ($0 \le k \le t$) to be fully delivered to their bases. If $k < t$, management also accepts $z$ of the $n_{k+1}$ robots from the next batch, the $(k+1)$-th one ($0 \le z < n_{k+1}$).

Management maximizes $k$ first and then maximizes $z$.

The first line contains $w$, $h$, $s$, and $q$, where $1 \le w, h \le 10^5$, $1 \le s \le 4$, and $1 \le q \le 100$. The next $s$ lines each contain the coordinates $x_i$ and $y_i$ of a base, where $1 \le x_i \le w$ and $1 \le y_i \le h$. The next line contains the number of batches $t$, where $1 \le t \le 100$. The next $t$ lines each contain $b_j$, $n_j$, and $m_j$, where $1 \le b_j \le s$, $1 \le n_j \le w \cdot h \cdot q$, and $0 \le m_j < \max(w, h)$.

In the sample, the whole first batch is accepted, and 7 robots from the second batch are accepted as well. Fig. 2 shows a placement where every cell holds at most one robot. Bases are drawn as circles. Cells with robots from base 1 are hatched vertically, and cells with robots from base 2 are gray.