← 返回题目列表

Codeforces · 1601/D

D. 困难山

中文机器翻译题面 查看原题

一群$$$n$$$登山者刚刚到达山脚。攀登这座山的初始难度可以用整数$$$d$$$来形容。

每个登山者都可以用两个整数$$$s$$$和$$$a$$$来描述,其中$$$s$$$是他的登山技巧,$$$a$$$是他的整洁程度。

技能水平为 $$$s$$$ 的登山者只有在 $$$p \leq s$$$ 时才能够攀登难度为 $$$p$$$ 的山峰。当登山者爬山时,它们会影响路径,从而可能改变登山难度。具体来说,如果一个整洁的登山者$$$a$$$攀登了一座难度为$$$p$$$的山,那么这座山的难度就变成了$$$\max(p, a)$$$。

登山者将一座座山峰攀登。在开始之前,他们想知道,如果选择正确的顺序,最多能有多少名登山者能够攀登这座山。由于您是小组中唯一进行编程的人,因此您需要回答这个问题。

注意,选择顺序后,每位能够登山的登山者都必须在当时登山。

输入

第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \leq n \leq 500\,000$$$; $$$0 \leq d \leq 10^9$$$) – 登山者的数量和山峰的初始难度。

接下来的 $$$n$$$ 行包含两个整数 $$$s_i$$$ 和 $$$a_i$$$ ($$$0 \leq s_i, a_i \leq 10^9$$$),它们定义了第 $$$i$$$ 登山者的攀登技巧和整洁度。

输出

打印一个整数,该整数等于可以登山的最大人数(如果他们选择正确的顺序)。

示例

输入 #1

3 2
2 6
3 5
5 7

输出 #1

2

输入 #2

3 3
2 4
6 4
4 6

输出 #2

2

输入 #3

5 0
1 5
4 8
2 7
7 6
3 2

输出 #3

3

注意

在第一个示例中,登山者 $$$2$$$ 和 $$$3$$$ 按此顺序即可登山。没有其他方法可以得到$$$2$$$ 的答案。

在第二个示例中,登山者 $$$1$$$ 由于山峰的初始难度而无法攀爬,而登山者 $$$2$$$ 和 $$$3$$$ 可以按任何顺序向上。

在第三个示例中,登山者可以按此特定顺序 $$$5$$$、$$$3$$$ 和 $$$4$$$ 攀登这座山。没有其他方法可以达到最佳答案。