Sauna

Time limit2sMemory limit1024 MB

Summary

Given n friend intervals and a limit t, choose Max's stay of length at most t to maximize friends he outranks minus friends who outrank him.

Level: Medium6 of 10
Topics: Sorting, Segment tree, Two pointers
Solved: No attempts yet

Statement

Max loves going to the sauna with his friends. Today he visited the sauna again and brought $n$ friends. Each friend enters the steam room exactly once, and the time interval each friend spends there is known (time is measured in seconds from the moment of arrival at the sauna). Max also wants to enter the steam room exactly once, but he has not yet decided when.

Max cares about his reputation. From the point of view of the people in the sauna, person $A$ is cooler than person $B$ if $A$ entered the steam room strictly earlier than $B$ and left strictly later than $B$ , which shows that $A$ is more persistent. Max's reputation is the number of people who are less cool than him minus the number of people who are cooler than him.

Max cannot stay in the steam room for more than $t$ seconds. Help him choose the time interval for his stay that makes his reputation as large as possible.

Input

The first line contains two integers $n$ and $t$ ( $1 \leq n \leq 2 \cdot 10^5$ , $1 \leq t \leq 10^9$ ), the number of Max's friends and the maximum time Max can spend in the steam room.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ( $0 \leq l_i < r_i \leq 10^9$ ), the arrival and departure times of friend $i$ .

All $l_i$ and $r_i$ are non-negative integers, but the endpoints of Max's time interval do not have to be integers or non-negative.

Output

Print one number, the maximum reputation Max can get while staying in the steam room for at most $t$ seconds.

Hints

In the first example, Max can arrive at time $0.5$ and leave at time $9.5$ , which makes him cooler than all of his friends.

In the second example, Max cannot be cooler than all of his friends, but he can arrive at time $0.3$ and leave at time $7.1$ . Then he is cooler than friends $1$ and $2$ but not friend $3$ . Friend $3$ is not cooler than Max either, so the answer is $2$ .

In the third example, Max can be cooler only than friend $2$ , but then he is less cool than friend $1$ . So a reputation greater than $0$ is impossible.

In the fourth example, Max gets reputation $0$ if he arrives before all of his friends or after all of them.

Examples4

Example 1
Input
```
3 9
1 7
4 6
5 9
```
Expected output
```
3
```
Example 2
Input
```
3 7
1 7
4 6
5 9
```
Expected output
```
2
```
Example 3
Input
```
3 3
1 7
4 6
5 9
```
Expected output
```
0
```
Example 4
Input
```
3 1
1 7
4 6
5 9
```
Expected output
```
0
```