题目描述

题目译自 BalticOI 2024 Day2「Fire」

在古老的波罗的海宗教中，燃烧圣火非常重要。一位叫 krivis 的祭司负责保护圣火不熄灭。他有许多值得信赖的助手，称为 vaidilutės，他想给她们建立一个日程表来给火添加燃料并保护火种。他必须确保圣火总是由一些助手来维护。

Krivis 有自己的时间测量系统，每天有 $M$ 分钟。他的村子里有 $N$ 个 vaidilutės。第 $i$ 个 vaidilutė 的可能工作时间由两个整数 $s_i$ 和 $e_i$ 描述。$s_i$ 是她一天中最早开始工作的时间，$e_i$ 是她一天中最晚结束工作的时间。时间以分钟为单位，从一天的开始算起。请注意，当 $s_i > e_i$ 时，表示这个 vaidilutės 愿意通宵工作。

Krivis 要求你选择一些 vaidilutės 并为她们安排轮班。被选中的 vaidilutės 必须在不早于时间 $s_i$ 的情况下开始值班，在不晚于时间 $e_i$ 的情况下结束值班。单次值班时间总比一天的长度短。被选中的 vaidilutė 将每天重复轮班。

从一个 vaidilutė 交接给另一个 vaidilutė 会增加火灭掉的风险。因此，你希望将这种情况在一天中发生的次数降到最低，也就是安排尽可能少的 vaidilutė。

计算你需要选择的 vaidilutė 人数的最小值，满足圣火每时每刻都被维护。

输入格式

第一行两个整数 $N$ 和 $M$，表示 vaidilutė 的人数和一天的时间长度。

接下来 $N$ 行，第 $i$ 行包含两个整数 $s_i$ 和 $e_i$，分别表示第 $i$ 个 vaidilutė 的最早开始时间和最晚结束时间。

输出格式

输出一个整数，表示你需要选择 vaidilutė 的人数最小值。如果不可能选出一些 vaidilutė 满足要求，输出 $-1$。

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1

数据范围与提示

对于所有数据，满足：

• $1\le N\le 2\cdot 10^5$
• $2\le M\le 10^9$
• $0\le s_i,e_i<M$（对于所有 $1\le i\le N$）
• $s_i\neq e_i$（对于所有 $1\le i\le N$）

详细子任务附加限制及分值如下表所示。