사우나

시간 제한2초메모리 제한1024 MB

요약

친구 n명의 체류 구간과 최대 체류 시간 t가 주어질 때, Max가 t초 이하로 머무는 구간을 골라 자신보다 덜 멋진 사람 수에서 더 멋진 사람 수를 뺀 값을 최대로 만듭니다.

난이도: 보통10점 중 6점
유형: 정렬, 세그먼트 트리, 투 포인터
정답자: 아직 제출이 없습니다

문제

맥스는 친구들과 함께 사우나에 가는 것을 아주 좋아합니다. 오늘도 그는 친구 $n$ 명을 데리고 사우나에 갔습니다. 각 친구는 증기실에 정확히 한 번 들어갑니다. 각 친구가 증기실에 머무는 시간 구간은 알려져 있습니다(사우나에 도착한 순간부터 초 단위로 잽니다). 맥스도 증기실에 정확히 한 번 들어가고 싶지만, 언제 들어갈지는 아직 정하지 않았습니다.

맥스는 자신의 평판을 신경 씁니다. 사우나에 있는 사람들의 눈으로 보면, 사람 $A$ 가 사람 $B$ 보다 증기실에 엄격히 먼저 들어가고 엄격히 나중에 나왔다면 $A$ 는 $B$ 보다 멋있습니다. 그만큼 $A$ 가 더 끈기 있다는 뜻입니다. 맥스의 평판은 그보다 덜 멋있는 사람의 수에서 그보다 더 멋있는 사람의 수를 뺀 값입니다.

맥스는 증기실에 $t$ 초를 넘게 머물 수 없습니다. 평판이 가장 커지도록 맥스가 머물 시간 구간을 고르도록 도와주세요.

입력

첫 줄에 정수 $n$ 과 $t$ 가 주어집니다( $1 \leq n \leq 2 \cdot 10^5$ , $1 \leq t \leq 10^9$ ). $n$ 은 맥스의 친구 수이고, $t$ 는 맥스가 증기실에 머물 수 있는 최대 시간입니다.

다음 $n$ 개 줄에는 각각 정수 $l_i$ 와 $r_i$ 가 주어집니다( $0 \leq l_i < r_i \leq 10^9$ ). 각각 친구 $i$ 의 도착 시각과 퇴장 시각입니다.

모든 $l_i$ 와 $r_i$ 는 음이 아닌 정수이지만, 맥스의 시간 구간 양 끝은 정수이거나 음이 아닐 필요가 없습니다.

출력

하나의 수를 출력합니다. 맥스가 $t$ 초 이하로 사우나에 머물 때 얻을 수 있는 평판의 최댓값입니다.

힌트

첫 번째 예시에서 맥스는 시각 $0.5$ 에 도착하고 시각 $9.5$ 에 나갈 수 있습니다. 이렇게 하면 그는 친구 모두보다 멋있어집니다.

두 번째 예시에서 맥스는 친구 모두보다 멋있어질 수는 없습니다. 하지만 예를 들어 시각 $0.3$ 에 도착해 시각 $7.1$ 에 나갈 수 있습니다. 그러면 친구 $1$ 과 $2$ 보다는 멋있지만 친구 $3$ 보다는 멋있지 않습니다. 친구 $3$ 도 맥스보다 멋있지 않으므로 답은 $2$ 입니다.

세 번째 예시에서 맥스는 친구 $2$ 보다만 멋있을 수 있습니다. 그런데 그렇게 되면 친구 $1$ 보다 덜 멋있게 됩니다. 따라서 평판을 $0$ 보다 크게 얻는 것은 불가능합니다.

네 번째 예시에서 맥스가 친구들보다 먼저 들어가거나 모두보다 나중에 들어가면 평판은 $0$ 이 됩니다.

예제4

예제 1
입력
```
3 9
1 7
4 6
5 9
```
예상 출력
```
3
```
예제 2
입력
```
3 7
1 7
4 6
5 9
```
예상 출력
```
2
```
예제 3
입력
```
3 3
1 7
4 6
5 9
```
예상 출력
```
0
```
예제 4
입력
```
3 1
1 7
4 6
5 9
```
예상 출력
```
0
```