← 返回题目列表

Codeforces · 930/C

C. 特奥多不是骗子!

中文机器翻译题面 查看原题

年轻的特奥多喜欢绘画。他最喜欢的爱好是在巨大的 [1;m] 段内绘制带有整数边框的段。有一天,Teodor 注意到他刚刚画的图有一个有趣的特征:不存在属于图中每个线段的整数点。发现这一事实后,特奥多决定与萨莎分享。

Sasha知道Teodor喜欢炫耀,所以他从不信任他。 Teodor想要证明自己有时是可以信任的,所以他决定说服Sasha,他的图片中不存在这样的整数点,它属于每个段。然而Teodor是个懒人,既不愿意告诉Sasha所有线段末端的坐标,也不愿意告诉他它们的数量,所以他建议Sasha问他一系列问题“给定整数点xi,Fedya的图片中有多少个线段包含该点?”,并承诺说出这个问题的正确答案。

两个男孩都很忙学习,没有太多时间,所以他们要求你找出萨沙可以问特奥多多少个问题,只有对他的问题的答案,萨沙不能确定特奥多是否在骗他。请注意,萨莎不知道特奥多图片中的片段数量。当然,萨沙是个聪明人,同一件事从来不会问两次。

输入

输入的第一行包含两个整数:n 和 m (1 ≤ n, m ≤ 100 000) — Teodor 图片的片段数量以及 Sasha 可以询问的点的最大坐标。

接下来 n 行的第 i 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ m) - 图片中第 i 段的左端和右端。请注意,线段的左端和右端可以是同一点。

保证不存在属于所有段的整数点。

输出

单行输出应包含一个整数 k – 最大集合 (xi, cnt(xi)) 的大小,其中所有 xi 都不同,1 ≤ xi ≤ m,并且 cnt(xi) 是线段数量,包含坐标为 xi 的点,这样,如果他只知道该集合(并且不知道 n),则无法确定不存在属于初始图片中所有线段的点。

示例

输入 #1

2 4
1 2
3 4

输出 #1

4

输入 #2

4 6
1 3
2 3
4 6
5 6

输出 #2

5

注意

第一个例子显示了 Sasha 永远无法确定 Teodor 没有对他撒谎的情况,因为即使知道线段 [1;4] 中每个点的 cnt(xi),他也无法区分这种情况与 Teodor 绘制了整个 [1;4] 线段的情况。

在第二个示例中,Sasha 可以询问大约 5 点,例如1、2、3、5、6,仍然不确定Teodor是否对他撒了谎。但一旦知道了 [1;6] 段中所有点的信息,Sasha 就可以确定 Teodor 没有对他撒谎。