P14394 [JOISC 2016] 俄罗斯套娃 / Matryoshka

你打算开设一家销售俄罗斯套娃的商店。为此，你向工厂订购了 $N$ 个俄罗斯套娃。这些套娃被编号为 $1$ 至 $N$。其中第 $i$ 个套娃（$1 \le i \le N$）可以视为一个底面直径为 $R_i$ cm、高为 $H_i$ cm 的中空直圆柱体。每个套娃可以收纳一个底面直径和高度都比它小的其他套娃。被收纳的套娃内部还可以再收纳其他套娃。 某日，你收到工厂发来的通知：你订购的 $N$ 个套娃不能一次性全部做完，所以第一批只会送达直径大于等于 $A$ cm 并且高度小于等于 $B$ cm 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。 $A$ 和 $B$ 的值可能会突然更改。因此，你决定针对 $Q$ 组 $(A_j, B_j)$（$1 \le j \le Q$）求出没被套的套娃数量的最小值。询问互相独立。

从标准输入中读取以下数据： - 第 $1$ 行包含两个用空格分隔的整数 $N$ 和 $Q$。这表示你订购的俄罗斯套娃数量为 $N$ 个，同时将给出 $Q$ 组 $A$ 和 $B$ 的值。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含两个用空格分隔的整数 $R_i$ 和 $H_i$。这表示第 $i$ 个俄罗斯套娃的底面直径为 $R_i$ cm，高度为 $H_i$ cm。 - 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含两个用空格分隔的整数 $A_j$ 和 $B_j$。

输出共 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）输出 $A=A_j$ 且 $B=B_j$ 时，没有被套的套娃数量最小值。

### 样例 1 解释 - 当 $(A, B) = (10, 5)$ 时，不存在底面直径不小于 $10$ cm 且高度不超过 $5$ cm 的俄罗斯套娃，因此输出 $0$。 - 当 $(A, B) = (3, 5)$ 时，底面直径不小于 $3$ cm 且高度不超过 $5$ cm 的俄罗斯套娃为第 $1$ 号和第 $7$ 号。第 $7$ 号套娃可以被收纳进第 $1$ 号套娃中。此时，未被任何套娃收纳的套娃的最小数量为 $1$。 - 当 $(A, B) = (3, 9)$ 时，底面直径不小于 $3$ cm 且高度不超过 $9$ cm 的俄罗斯套娃为第 $1$ 号、第 $2$ 号、第 $3$ 号和第 $7$ 号。此时，可以将第 $7$ 号套娃收纳进第 $1$ 号套娃中，再将第 $1$ 号套娃收纳进第 $3$ 号套娃中。未被任何套娃收纳的套娃的最小数量为 $2$。 ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 200\,000$。 - $1 \le Q \le 200\,000$。 - $1 \le R_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le H_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le A_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。 - $1 \le B_j \le 1\,000\,000\,000$（$1 \le j \le Q$）。 ### 子任务 **子任务 1 [11 分]** 满足以下条件： - $N \le 10$。 - $Q = 1$。 **子任务 2 [15 分]** 满足以下条件： - $N \le 100$。 - $Q = 1$。 **子任务 3 [25 分]** 满足以下条件： - $N \le 2\,000$。 - $Q \le 2\,000$。 **子任务 4 [49 分]** 无额外限制。 翻译由 Qwen3-235B 完成