← 返回题目列表

AtCoder · icpc2013summer_warmingUp_a

A. 动漫大师

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

说明

KM非常喜欢Anime(日本动画)。
他正在尝试观看尽可能多的动漫。
动画每周在同一时区播出。
因为他是一个完美主义者,所以他每周必须看同样的动漫。
此外,他无法观看同时播放的动画或通过录制动画稍后观看。
KM是一位非常优秀的数学家,但是因为很多动漫都在播放,所以他找不到这个问题的最佳解决方案。
优秀的程序员你能解决这个问题吗?

输入

输入文件的第一行包含 N 和 M (1 \leq N \leq 10^5, 2 \leq M \leq 10^6),分别是动漫的数量和一周的长度。
在 KM 的国家,一周由 M 单位时间。
以下各项 N 行给出开始时间 s 和结束时间 每个动漫的 t 。 (0 \leq s, t < M, s \neq t)
s > t 表示动画持续时间超过一周。
可以观看结束时间与开始时间相同的两部动画。

输出

输出他可以观看的动画的最大数量。

示例输入

3 10
0 3
3 7
7 0

示例输出

3

示例输入

3 10
0 5
2 7
6 9

示例输出

2

示例输入

5 10
1 6
2 7
3 8
4 9
5 0

示例输出

1