P4864 Jerry Loves Lines

Jerry 很喜欢在纸上面画直线呢。

Jerry 在纸上面画上了 $N$ 条直线，每一条直线都可以用 $y=k_ix+b_i$ 来表示。现在 Jerry 想知道对于 $M$ 条可以表示为 $X=A_j$ 的直线，从下往上数排名第 $K$ 的交点的 $y$ 坐标是多少。 如有 $x$ 条直线与一条 $X=A_j$ 的直线交于同一点，算 $x$ 个点。

第一行三个正整数 $N,M,K$。 接下来 $N$ 行，每一行两个非零整数 $k_i$ 和 $b_i$ 描述了一条直线。 接下来 $M$ 行，每行一个整数 $A_j$ 表示一个询问。

$M$ 行，每一行一个整数表示答案。

对于 $30\%$ 的数据，$1 \leqslant N,M \leqslant 2000$； 对于 $100\%$ 的数据，$1 \leqslant N \leqslant 2000$，$1 \leqslant M \leqslant 5\times10^5$。 其他所有读入的数全在 `int` 范围内，且保证 $1 \leqslant K \leqslant N$。 温馨提示：如果对自己的做法的常数感到不放心，请吸入氧气（食用 O2 优化）如果有着充足自信，尽管放手浪。 $\color{white}{\text{int*int会爆int!!!}}$