题目描述

农民约翰正在指挥他的 $N$ 头牛进行清理工作。
他将一天划分为了 $T$ 个班次（编号为 $1$ 到 $T$）。
每头牛都只能在一天中的某一个连续时间段内不间断地工作。

你需要帮助约翰安排奶牛的清理班次，使得每个班次（$1 \sim T$）都至少有一头牛在工作，并且动用的奶牛数量尽可能少。

输入格式

• 第 1 行：两个整数 $N$ 和 $T$，用空格隔开。
• 第 2 到 $N+1$ 行：每行两个整数 $l_i$ 和 $r_i$，表示第 $i$ 头牛的工作开始时间和结束时间（保证 $l_i \le r_i$）。

输出格式

• 如果可以实现每个班次都有奶牛工作，输出最少需要的奶牛数量；
• 否则，输出 $-1$。

数据范围

• $1 \le N \le 25000$
• $1 \le T \le 10^6$
• 每头牛的工作时间 $l_i, r_i$ 满足 $1 \le l_i \le r_i \le T$

输入样例

3 10
1 7
3 6
6 10

输出样例

2

样例解释

这里 $T = 10$，班次从 1 到 10。

奶牛数据：

1. 牛 1：工作时段 [1, 7]
2. 牛 2：工作时段 [3, 6]
3. 牛 3：工作时段 [6, 10]

要覆盖 [1, 10] 的每个整数时刻（班次），至少需要两头牛。
可以选择牛 1（覆盖 [1, 7]）和牛 3（覆盖 [6, 10]）。

• 时刻 1~7：牛 1 工作。
• 时刻 6~10：牛 3 工作。
• 时刻 6~7 有两头牛同时工作，但这不影响。
• 每个班次（1 到 10）都有牛覆盖。

如果只用一头牛，不可能覆盖全部 10 个时刻，所以最少数量为 2。