Chessboard Traversal with Vertical Move Budget

Consider an $N \times M$ chessboard (grid) in which $T$ cells are broken (i.e. unusable). In other words, you cannot place a chess piece on a broken cell. Justin invented the following game:

Initially, you may place chess pieces on some of the good (non‐broken) cells in the first column. No two pieces may occupy the same cell. After that, you may perform the following two types of operations repeatedly (in any order, and the vertical moves (operation 1) can be applied several times before a horizontal shift):

1. Choose one chess piece and move it vertically (one cell up or down) to an adjacent cell, but only if that cell is good and there is no other piece on it. Each such move counts as one operation of type 1.

2. Move all chess pieces one column to the right. However, this operation is only allowed if after the shift every piece lands in a good cell. (That is, if even one piece would land on a broken cell, the operation cannot be executed.)

The game is played as follows. After placing the pieces in the first column, you want to eventually move every piece to the last column (column $M$) by a sequence of moves. However, there is a limitation: the total number of type 1 moves performed (i.e. the sum over all pieces) must not exceed a given budget.

You are given $Q$ queries. Each query consists of an integer $k_i$; for that query, you are asked: what is the maximum number of pieces you can initially place in the first column such that, after some sequence of allowed moves, all pieces can be moved to the last column and the total number of type 1 moves used is at most $k_i$?

Additional Explanation

A chess piece that is moved only by horizontal moves would simply remain in the same row. However, if the cell in the next column in that row is broken, you may use one or more vertical moves (each moving a piece one cell up or down) so that upon shifting to the next column, it lands on a good cell. Note that the pieces must never collide, i.e. in every column the positions of the pieces must be all distinct.

For each column $j$ ($1 \le j \le M$) let $A_j$ be the set of row indices (from $1$ to $N$) that are not broken. When moving from column $j$ to column $j+1$, you must choose (for each piece) a cell in $A_{j+1}$ such that the overall assignment (when sorted by row) is consistent with the ordering of pieces. The cost incurred for a piece to go from row $r$ in column $j$ to row $r'$ in column $j+1$ is $|r - r'|$, which is exactly the number of vertical moves needed.

Your task is to compute, for each query $k_i$, the maximum integer $X$ (number of pieces) for which there exists a valid assignment of good cells $S_1,S_2,\dots,S_M$ with $|S_j| = X$ (and $S_j$ sorted in increasing order) satisfying $$ \sum_{j=1}^{M-1}\; \sum_{i=1}^{X} \; \big|S_j[i] - S_{j+1}[i]\big| \le k_i. $$ Note that $X$ is also upper–bounded by the minimum over $j$ of $|A_j|$.

inputFormat

The first line contains four integers $N$, $M$, $T$, and $Q$ ($1 \le N, M \le 100$, $0 \le T \le N \times M$, $1 \le Q \le 10^5$), representing the number of rows, the number of columns, the number of broken cells and the number of queries respectively.

The next $T$ lines each contain two integers $r$ and $c$ ($1 \le r \le N$, $1 \le c \le M$), indicating that the cell in row $r$ and column $c$ is broken. It is guaranteed that all broken cells are distinct.

The next $Q$ lines each contain a single integer $k_i$ ($0 \le k_i \le 10^9$), representing a query that asks: what is the maximum number of pieces you can place in the first column such that, following some valid sequence of moves, all pieces reach the last column and the total number of vertical moves does not exceed $k_i$?

outputFormat

For each query, output one integer on a separate line: the maximum number of pieces that can be successfully moved from the first to the last column under the given vertical move budget.

sample

3 3 1 2
2 2
1
2

2
2

</p>