Japan Alumni Group Summer Camp 2013 Warming Up

A - Anime Master


Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB

Description

KM really likes Anime (Japanese animation).
He is trying to watch as many animes as possible.
The anime is broadcast at the same time zone every week.
Because he is a perfectionist, he must watch the same animes every week.
Moreover he can't watch animes which are broadcast at the same time or watch them later by recording them.
KM is a really excellent mathematician but because a lot of animes are broadcast, he couldn't find the best solution for this problem.
Can you, the excellent programmer, solve this problem?

Input

The first line of the input file contains N and M (1 \leq N \leq 10^5, 2 \leq M \leq 10^6), which is the number of animes and the length of a week, respectively.
In KM's country, the week is composed of M unit time.
Each of the following N lines gives start time s and end time t of each animes. (0 \leq s, t < M, s \neq t)
s > t means the anime lasts over the boundary of the week.
It is possible to watch two animes whose end time is same as the other's start time.

Output

Output the maximal number of animes he can watch.

Sample Input

3 10
0 3
3 7
7 0

Sample Output

3

Sample Input

3 10
0 5
2 7
6 9

Sample Output

2

Sample Input

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

Sample Output

1

Source name

The First KMCMonthly Contest

Submit提出する