Robotic Deployment with Grid Capacity Constraints

In this problem, you are given a rectangular grid of size \(w \times h\) (with cells from \((1,1)\) to \((w,h)\)) that represents the mining area on a planet. There are \(s\) bases located on some grid cells. The \(i\)th base is at \((x_i, y_i)\). Robots are delivered in \(t\) batches. For the \(j\)th batch, all \(n_j\) robots are delivered to base number \(b_j\) and each robot has a movement ability of \(m_j\).

Once delivered, each robot may move up to \(m_j\) times. In each move, a robot can move into any of the eight adjacent cells (including diagonals). Hence, a robot delivered to a base located at \((x,y)\) with movement ability \(m\) can end up in any cell \((i,j)\) satisfying \[ \max(|i-x|,|j-y|) \le m \] (intersected with the grid boundaries).

After all moves, the robots are activated and start mining. However, every cell can accommodate at most \(q\) robots. During the movement phase the robots can occupy the same cell, but after activation no cell may contain more than \(q\) robots.

The project team plans to deploy robots batch by batch. They must choose a prefix of batches \(1,2,\ldots,k\) (with \(0 \le k \le t\)) and, if \(k < t\), they are allowed to take an extra \(z\) robots (with \(0 \le z < n_{k+1}\)) from batch \(k+1\). Note that if \(k=t\), then \(z=0\). The goal is to maximize \(k\) and, under that condition, maximize \(z\) such that it is possible to assign a destination cell to every deployed robot (from batches \(1..k\) plus the extra \(z\) from batch \(k+1\)) with the following conditions:

• Each robot from batch \(j\) can only be assigned to a cell \((i,j)\) that is reachable from its base \(b_j\); i.e. \(\max(|i-x_{b_j}|,|j-y_{b_j}|) \le m_j\).
• The total number of robots assigned to any cell does not exceed \(q\).

Your task is to compute the maximum possible \(k\) and, under that maximum, the maximum \(z\) such that an assignment exists.

inputFormat

The first line of input contains four integers: \(w\), \(h\), \(s\) and \(q\) (grid width, grid height, number of bases, and maximum robots per cell).

The next \(s\) lines each contain two integers \(x_i\) and \(y_i\), denoting the coordinates of the \(i\)th base.

The following line contains an integer \(t\), the number of robot batches.

Then \(t\) lines follow. The \(j\)th of these lines contains three integers \(b_j\), \(n_j\) and \(m_j\), representing that batch \(j\) is sent to base \(b_j\), has \(n_j\) robots and each robot has movement ability \(m_j\).

outputFormat

Output two integers: the maximum possible \(k\) and the corresponding maximum \(z\) (if \(k=t\), output \(z=0\)).

sample

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

2 2