区间覆盖

题目描述

数轴上有 $n$ 个闭区间 $[l_i, r_i]$。现在要从这些区间中选出若干个，使得对于 $1$ 到 $N$ 之间的每一个整数点 $j$，都至少存在一个被选中的区间满足 $l_i \le j \le r_i$。选出的区间之间可以重叠，每个区间最多只能被选一次。

请输出最少需要选多少个区间；如果无论如何都覆盖不了 $1$ 到 $N$ 的全部整数点，输出 $-1$。

输入格式

第一行两个整数 $n$ 与 $N$。

接下来 $n$ 行，每行两个整数 $l_i$ 与 $r_i$，保证 $l_i \le r_i$。

输出格式

一行一个整数，表示最少需要选择的区间个数；无解输出 $-1$。

样例

输入样例

3 10
1 4
4 7
7 10

输出样例

3

样例解释

三个区间首尾相接，恰好覆盖 $1$ 到 $10$，最少需要全部选中。

数据范围

$1 \le n \le 2 \times 10^5$，$1 \le N \le 10^9$，$1 \le l_i \le r_i \le 10^9$。