题目描述

题目译自 JOISC 2016 Day1 T1 「マトリョーシカ人形」

你开了一家卖俄罗斯套娃的店。因此，你向厂家订购了 $N$ 个俄罗斯套娃，这些娃娃被编号为 $1$ 到 $N$，其中第 $i$ 个套娃是一个的直径为 $R_i$ 高度为 $H_i$ 的直♂柱体 。每个俄罗斯套娃都只能套高和直径严格比他小的套娃。同时只要满足条件，俄罗斯套娃可以嵌套多次。

有一天，你收到了厂家的来电，告诉你你预定的 $N$ 个娃娃不能一次性全部做完。所以第一批只会送达直径大于等于 $A$ 并且高度小于等于 $B$ 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。

由于厂家经常搞大新闻，所以他会改变 $A$ 和 $B$ 的值，总共 $Q$ 次，因此你需要对每对 $(A,B)$ 都作出回答，询问之间互不干扰。

输入格式

第一行有两个整数 $N$ 和 $Q$ ，表示套娃的个数和 $(A,B)$ 的对数；
之后的 $N$ 行，每行两个数 $R_i$ 与 $H_i$ 表示第 $i$ 个数的直径和高度；
之后的 $Q$ 行，每行两个数 $A_i$ 与 $B_i$ 表示第 $i$ 个询问， $A_i$ 与 $B_i$ 的意思如上所示。

输出格式

输出包括 $Q$ 行，每行包括一个数字，为送来的套娃经过若干次嵌套后，没有被套的套娃数量最小的个数。

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 \leq N,Q \leq 2\times 10^5,1 \leq R_i,H_i,A_i,B_i \leq 10^9$。

具体子任务限制及得分情况如下表：