P5222 Game

Justin was playing with his board and pieces... Suddenly, he came up with a very interesting game.

The board can be seen as an $N \times M$ grid. ~~Because Justin is too strong,~~ he broke $T$ cells, meaning no piece can be placed on those cells. The game Justin came up with works like this: At the beginning, you may choose some unbroken cells in the first column and place one piece on each of them. Then, you may perform the following operations in order any number of times: 1. Choose one piece and move it up or down to an **adjacent** cell that is unbroken and **does not contain any other piece**. 2. Move all pieces to the next column. If, after moving to the next column, **any** piece lands on a broken cell, then this operation cannot be performed. Justin now gives you $Q$ queries. Each time you are given a $k_i$, asking: what is the maximum number of pieces you can place in the first column such that, after some operations, you can move all pieces to the last column, and the total number of operation 1 performed by **all pieces combined** is at most $k_i$. (Thanks to ywwywwyww for finding an issue in the statement. It has now been fixed.)

The first line contains four positive integers: $N$, $M$, $T$, $Q$. The next $T$ lines each contain two positive integers $x_i$, $y_i$, indicating a broken cell. The next $Q$ lines each contain one positive integer $k_i$, representing Justin's $i$-th query.

Output $Q$ lines, each containing a non-negative integer indicating the answer to each query.

In the first sample: When the limit is $0$, you can place one piece at $(3,1)$, then keep performing operation 2. When the limit is $1$, you can place one piece at $(3,1)$ and another at $(2,1)$. After performing operation 2 twice, perform operation 1 once on the piece at $(2,3)$ to move it to $(1,3)$, then keep performing operation 2. When the limit is $2$, it is the same as above. Because if you place three pieces, you cannot perform operation 2. In the second sample: You can see it is completely blocked, so it is impossible to move to the last column. Constraints: |Test Point ID|$N\le$|$M\le$|$T\le$|$Q\le$| |:-------:|:-------:|:-------:|:-------:|:-------:| |$1$|$1$|$10^6$|$1$|$10^5$| |$2-6$|$10$|$100$|$10$|$100$| |$7-10$|$20$|$100$|$50$|$10^3$| |$11-14$|$30$|$10^4$|$100$|$10^4$| |$15-20$|$50$|$10^6$|$10^3$|$10^5$| $$1 \le x_i \le N \qquad 1\le y_i \le M \qquad 0 \le k_i \le 2^{31}-1$$ The testdata for test points $11$~$20$ is randomly generated. Translated by ChatGPT 5