下界熔炼
题面描述
炼金学家 Dr. Alchem 发现了一鼎奇怪的熔炉，这顶熔炉利用了炼狱燃料，能够在很快时间内炼制出一些奇异的金属。为了测试这鼎熔炉的效果，Dr. Alchem 决定进行 次实验。
每一次实验都可以用 两个参数描述，表示在 时刻往熔炉里放一块炉石，然后在第 时刻将炉石拿出。
这鼎熔炉唯一与外界相通的地方是它的盖子。只有当盖子打开时，Dr. Alchem 才能往里面放炉石或者拿炉石出来。由于这个盖子过于危险，Dr. Alchem 决定尽量少地操作盖子。他将这样进行第 次实验：
-
在第 时刻把盖子打开（如果已经打开了则不重复打开），并且往熔炉里放入一块炉石。
-
在第 时刻，如果盖子不是打开的，则实验会失败。
否则他会将一块炉石拿出来，此时他可以决定是否把盖子盖上。
这么做仍然有风险。因为长时间打开盖子会让炼狱燃料泄露，造成巨大的浪费，所以 Dr. Alchem 希望盖子打开的时间尽量少。正巧，Dr. Alchem 的好友送来了 个二次性操作装置，Dr. Alchem 可以将这 个装置应用在 个不同的实验上，使得这些实验可以有不同的操作方式：
- 在第 时刻将一个炉石瞬移放入熔炉，此刻并不需要盖子是开着的。并且，此时他可以选择将盖子盖上或打开。
- 在第 时刻将一个炉石瞬移拿出熔炉，此刻并不需要盖子是开着的。并且，此时他可以选择将盖子盖上或打开。
由于实验太多了，Dr. Alchem 打不定主意。所以他来请教你，希望你告诉他，在所有实验都成功的前提下，盖子最短需要打开多久。在这里，可以认为放入、拿出炉石以及盖上、打开盖子都不需要时间。
输入格式
第一行两个正整数 ，表示实验的个数、二次性操作装置的数量。
接下来 行，每行两个整数 ，表示第 个实验的开始与结束时间。
输出格式
一个整数，表示盖子最短需要打开的时间。
样例
2 1
1 3
2 4
2
说明/提示
Dr. Alchem 可以把装置用在第一个实验上：
- 在时刻 ，他将炉石瞬移放入熔炉。
- 在时刻 ，他打开熔炉的盖子，放入一块炉石。
- 在时刻 ，他将炉石瞬移拿出熔炉。
- 在时刻 ，他将炉石拿出熔炉，并且盖上盖子。
熔炉的盖子在 时刻内是开着的，打开时间为 。可以证明，没有更短的方法。
对于 的数据，。对于所有 ，满足 ，并且所有的 互不相同（这 个数没有重复的数）。
数据有梯度。
国庆提高/省选组比赛
- Status
- Live... (Attended)
- Rule
- IOI
- Problem
- 40
- Start at
- 2025-10-15 19:32
- End at
- 2025-11-16 0:00
- Duration
- 1104 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 85