충전 뒤의 정리 시간

문제

작은 전기차 충전소에는 충전기 한 대가 있다. 운영자는 하루 동안 들어온 N개의 예약 요청 중 일부를 승인하려 한다. 각 요청에는 충전을 시작할 시각 s와 끝낼 시각 e가 정해져 있다. 시각은 하루의 시작을 기준으로 센 정수 단위이며, 모든 요청에서 s는 e보다 작다. 승인한 요청은 정해진 시작 시각부터 종료 시각까지 충전기를 사용해야 하며, 시작이나 종료 시각을 바꿀 수 없다. 이 충전소에서는 차량 한 대의 충전이 끝날 때마다 케이블과 주변 공간을 정리한다. 정리에는 항상 C만큼의 시간이 필요하다. 종료 시각이 e인 요청을 승인했다면 다음 차량의 충전은 e+C 이상인 시각에만 시작할 수 있다. 정확히 e+C에 시작하는 것은 가능하다. C가 0이면 앞 차량의 종료 시각과 뒤 차량의 시작 시각이 같아도 두 요청을 모두 승인할 수 있다. 충전기는 하루의 시작 시각인 0에 바로 사용할 수 있다. 첫 번째로 승인한 요청 앞에는 정리 시간이 필요하지 않다. 마지막으로 승인한 요청 뒤의 정리가 언제 끝나는지는 승인 가능 여부에 영향을 주지 않는다. 입력에 주어진 요청은 시간순으로 정렬되어 있지 않을 수 있으며, 시작과 종료 시각이 모두 같은 요청이 여러 개 들어올 수도 있다. 이러한 요청도 각각 서로 다른 차량의 요청으로 취급한다. 운영자는 충전 시간의 합이나 수익이 아니라 승인한 요청의 개수를 최대화하려 한다. 요청 하나를 여러 번 승인할 수는 없고, 승인하지 않은 요청은 충전기 사용에 아무런 영향을 주지 않는다. 최대 개수를 만드는 선택이 여러 개라면 어느 선택을 사용해도 되며, 선택한 차량의 목록은 출력하지 않는다. 예약 요청과 공통 정리 시간이 주어졌을 때 승인할 수 있는 요청의 최대 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 요청의 개수 N과 정리 시간 C가 공백으로 구분되어 주어진다. N과 C는 정수이며 0 ≤ N ≤ 40,000, 0 ≤ C ≤ 999이다.
다음 N개 줄에는 각 요청의 시작 시각 s와 종료 시각 e가 주어진다. s와 e는 정수이며 0 ≤ s < e ≤ 999이다. N이 0이면 요청을 나타내는 줄은 없다.

출력

승인할 수 있는 요청의 최대 개수를 한 줄에 출력한다. 요청이 하나도 없으면 0을 출력한다.

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

3

4 0
2 4
0 2
2 4
4 5

3

0 7

0

출처: Devin.KR 자체 제작