CF1601D Difficult Mountain

题目描述

$n$ 个人相约去爬山。 山的初始攀登难度为 $d$。 每位登山者有两个属性:技巧 $s$ 和整洁度 $a$。 技巧为 $s$ 的登山者能登上攀登难度为 $p$ 的山当且仅当 $p\leq s$。 在一位整洁度为 $a$ 的登山者登上攀登难度为 $p$ 的山后,山的攀登难度会变为 $\max(p,a)$。 请给这些登山者指定一个爬山的先后顺序,最大化登上山的人数。 如果轮到一位登山者时他能登上山,则他一定会选择登山。

输入格式

第一行两个整数 $n,d$($1\leq n\leq 5\times10^5$,$0\leq d\leq10^9$)。 接下来 $n$ 行每行两个整数 $s_i,a_i(0\leq s_i,a_i\leq 10^9)$,描述第 $i$ 个登山者的信息。

输出格式

一行一个整数,为登上山的人数的最大值。

说明/提示

In the first example, alpinists $ 2 $ and $ 3 $ can climb the mountain if they go in this order. There is no other way to achieve the answer of $ 2 $ . In the second example, alpinist $ 1 $ is not able to climb because of the initial difficulty of the mountain, while alpinists $ 2 $ and $ 3 $ can go up in any order. In the third example, the mountain can be climbed by alpinists $ 5 $ , $ 3 $ and $ 4 $ in this particular order. There is no other way to achieve optimal answer.