진료실 정리 시간을 포함한 예약

문제

한 병원은 하루 동안 사용할 진료실 하나의 예약을 확정하려 한다. 접수된 예약 요청마다 원하는 진료 시작 시각과 종료 시각이 정해져 있다. 병원은 각 요청을 그대로 받아들이거나 거절할 수 있으며, 요청에 적힌 시작 시각이나 종료 시각을 바꾸거나 진료를 여러 구간으로 나누어 진행할 수는 없다. 진료실은 한 번에 한 예약에만 사용할 수 있다. 또한 진료 하나가 끝날 때마다 다음 진료를 준비하기 위해 정확히 C만큼의 정리 시간이 필요하다. 모든 예약의 정리 시간은 같다. 어떤 예약의 종료 시각이 e라면 그 예약을 받은 뒤에는 시각 e+C부터 다른 예약의 진료를 시작할 수 있다. 다음 예약의 시작 시각이 정확히 e+C인 경우에도 두 예약을 함께 받을 수 있다. 하루의 첫 진료 전에는 정리 시간이 필요하지 않다. 마지막 진료 뒤에도 정리 작업은 하지만, 정리 작업을 끝내야 하는 별도의 마감 시각은 없다. 따라서 마지막 예약은 종료 시각 뒤에 C만큼의 시간이 추가로 필요하다는 이유로 거절하지 않는다. 예약을 하나도 받지 않는 선택도 허용한다. 병원은 진료 시간이 짧거나 긴 요청을 따로 우대하지 않는다. 예약을 하나 받아들이면 진료 시간과 관계없이 확정한 예약 수가 정확히 하나 늘어난다. 같은 시작 시각과 종료 시각을 가진 요청이 여러 개 있어도 서로 다른 환자의 요청으로 취급한다. 다만 시간이 겹치는 요청을 동시에 받을 수는 없다. 접수 목록은 시간순으로 정렬되어 있지 않다. 병원은 전체 요청을 확인한 뒤 서로 충돌하지 않는 요청들을 골라 가장 많은 예약을 확정하려 한다. 두 요청의 진료 구간이 겹치지 않더라도 그 사이에 필요한 정리 시간을 확보하지 못하면 함께 선택할 수 없다는 점에 유의한다. 주어진 모든 요청과 정리 시간을 바탕으로 확정할 수 있는 예약 수의 최댓값을 구한다. 최대 개수를 만드는 선택이 여러 개이면 어느 선택을 사용하는지는 출력에 영향을 주지 않는다.

입력

첫째 줄에 예약 요청 수 N과 정리 시간 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 1 ≤ N ≤ 100,000, 0 ≤ C ≤ 1,000,000,000이다.
다음 N개 줄에 각 요청의 시작 시각 s와 종료 시각 e가 공백으로 구분되어 주어진다. s와 e는 정수이며 0 ≤ s < e ≤ 1,000,000,000이다. 입력 순서는 예약의 우선순위를 뜻하지 않는다.

출력

확정할 수 있는 예약 수의 최댓값을 정수 하나로 출력한다.

5 2
0 3
4 5
5 7
9 10
1 8

3

4 0
2 4
0 2
1 3
4 5

3

3 10
0 1
0 1
2 3

1

출처: Devin.KR 자체 제작