자전거 최소 대수

문제

공유 자전거 대여소 한 곳에 자전거를 몇 대 준비해야 하는지 정하려 한다. 내일 이용 예약이 N건 들어와 있고, i번째 이용자는 시각 s_i에 자전거를 꺼내 시각 e_i에 반납한다. 항상 s_i < e_i이다. 반납된 자전거는 점검과 충전을 거쳐야 하며 이 작업에 정확히 G만큼의 시간이 걸린다. 따라서 시각 e_i에 반납된 자전거는 시각 e_i + G 이전에는 다른 사람이 쓸 수 없고, 시각 e_i + G부터는 쓸 수 있다. 즉 어떤 이용자가 시각 e_i + G와 같은 시각 s_j에 자전거를 꺼내는 것은 가능하다. G가 0이면 반납 즉시 다시 쓸 수 있다. 이용자 한 명은 자전거 한 대만 사용하며, 대여소에는 처음에 원하는 만큼의 자전거를 둘 수 있고 모두 점검이 끝난 상태이다. 어느 예약에 어느 자전거를 배정할지는 마음대로 정할 수 있다. 예약을 하나도 거절하지 않고 모두 처리하려면 최소 몇 대의 자전거가 필요한지 구하시오.

입력

첫 줄에 정수 N과 G가 공백으로 구분되어 주어진다. 다음 N개의 줄에 i번째 예약의 s_i와 e_i가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ G ≤ 10^9, 0 ≤ s_i < e_i ≤ 10^9이다. 모든 값은 정수이다.

출력

필요한 자전거의 최소 대수를 정수 하나로 출력한다.

4 2
1 4
2 5
6 8
7 9

2

3 0
0 5
5 10
10 15

1

1 1000
3 4

1

출처: Devin.KR 자체 제작