P4864 Jerry Loves Lines

Jerry really likes drawing straight lines on paper.

Jerry has drawn $N$ lines on paper. Each line can be written as $y = k_i x + b_i$. Now Jerry wants to know, for each of the $M$ lines that can be written as $X = A_j$, what the $y$-coordinate is of the intersection point that ranks $K$-th when counted from bottom to top. If $x$ lines intersect a line $X = A_j$ at the same point, it is counted as $x$ points.

The first line contains three positive integers $N, M, K$. The next $N$ lines each contain two non-zero integers $k_i$ and $b_i$, describing one line. The next $M$ lines each contain one integer $A_j$, representing a query.

Output $M$ lines. Each line contains one integer, representing the answer.

For $30\%$ of the testdata, $1 \leqslant N, M \leqslant 2000$. For $100\%$ of the testdata, $1 \leqslant N \leqslant 2000$, $1 \leqslant M \leqslant 5 \times 10^5$. All other input numbers are within the `int` range, and it is guaranteed that $1 \leqslant K \leqslant N$. Friendly reminder: if you are not confident about the constant factor of your solution, please inhale oxygen (use O2 optimization). If you are fully confident, go ahead and do whatever you want. $\color{white}{\text{int*int会爆int!!!}}$ Translated by ChatGPT 5