Problem H
Alehouse
Making friends can seem impossible, but going to the alehouse makes it easy — it is actually the only way to make friendships. Luckily, the alehouse is extremely good at its task: if two people are inside simultaneously, they instantly become friends. People even become friends if they meet each other in the door as one leaves and one enters the alehouse!
In Consistentville, each of its $n$ residents goes to the alehouse exactly once each week, and always during the same milliseconds as the week before. This is convenient for everyone, since then nobody needs to befriend new people all the time, which can be quite exhausting.
You are contemplating a move to Consistentville in order to adopt their well-ordered lifestyle, and have decided that you want as many friends as possible. However, you don’t actually enjoy ale that much, so you decide to limit your weekly visit at the alehouse to at most $k$ milliseconds. What is the maximum number of friends you can get?
Input
The first line of input contains two positive integers $n$ ($1 \leq n \leq 100\, 000$), and $k$ ($0 \leq k < 604\, 800\, 000$). The next $n$ lines describe at which millisecond each of the original residents of Consistentville enters and leaves the alehouse every week. Specifically, the $i^{\text {th}}$ line consists of two integers $a_ i$ and $b_ i$ ($0 \leq a_ i \leq b_ i < 604\, 800\, 000$) indicating that the $i^{\text {th}}$ resident enters the alehouse at millisecond $a_ i$ and leaves the alehouse at millisecond $b_ i$ each week.
Output
A single integer, the maximum number of friends you can get.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 0 2 1 8 5 9 2 4 7 8 10 10 |
4 |
