区间覆盖

题目描述

给定一条目标线段 [1, T] 和 n 个区间 [l_i, r_i]（保证 l_i ≤ r_i）。你需要从这 n 个区间中选择尽可能少的区间，使得它们的并集能够完全覆盖目标线段 [1, T]（即对于任意实数 x ∈ [1, T]，都存在至少一个被选择的区间包含 x）。如果无法覆盖整个线段，输出 -1。

输入格式

第一行包含两个整数 n 和 T（1 ≤ n ≤ 2×10^5，1 ≤ T ≤ 10^9）。 接下来 n 行，每行两个整数 l_i 和 r_i（1 ≤ l_i ≤ r_i ≤ 10^9）。

输出格式

输出一个整数，表示最少需要选择的区间数量。如果无法覆盖 [1, T]，输出 -1。

样例

输入：

3 10
1 5
4 8
7 10

输出：

3

说明：选择 [1,5]、[4,8] 和 [7,10] 可以覆盖 [1,10]，需要 3 个区间。注意 [1,5] 和 [7,10] 不能覆盖 (5,7) 之间的部分。

数据范围

• 对于 30% 的数据，n ≤ 20，T ≤ 100。
• 对于 60% 的数据，n ≤ 2000，T ≤ 10^6。
• 对于 100% 的数据，1 ≤ n ≤ 2×10^5，1 ≤ T ≤ 10^9，1 ≤ l_i ≤ r_i ≤ 10^9。