题目描述

你打算开设一家销售俄罗斯套娃的商店。为此，你向工厂订购了 $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$），在提前交付的套娃被放入盒子保管时，求出未被任何套娃收纳的套娃的最小数量。

题目

给定每个俄罗斯套娃的底面直径和高度信息，以及 $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_j, B_j)$，在将提前交付的俄罗斯套娃放入盒子保管时，未被任何套娃收纳的套娃的最小数量。

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

0
1
2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

3
1
3
5
0
2
1
3

提示

样例 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 完成