Japan Alumni Group Summer Camp 2013 Warming Up
A - Anime Master
Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB
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?
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 the maximal number of animes he can watch.
The First KMCMonthly Contest