지원 담당자의 정리 시간

문제

한 회사의 사내 IT 지원실에는 현장 지원을 맡는 담당자가 한 명 있다. 여러 부서가 같은 날 지원을 요청했으며, 각 요청에는 담당자가 작업을 시작해야 하는 시각과 작업을 마치는 시각이 정해져 있다. 지원실은 이 중 일부 요청을 골라 담당자에게 배정하려 한다. 요청을 선택하면 정해진 시작 시각부터 종료 시각까지 작업 전체를 수행해야 하며, 시작을 늦추거나 작업을 중간에 나누어 수행할 수 없다. 담당자는 작업 하나를 마친 뒤 장비를 정리하고 다음 작업을 준비하는 데 정확히 C만큼의 시간이 필요하다. 따라서 종료 시각이 e인 요청을 수행했다면, 다음으로 수행하는 요청의 시작 시각은 e+C 이상이어야 한다. 시작 시각이 정확히 e+C인 요청은 수행할 수 있다. 이동에 필요한 시간은 이 정리 시간에 모두 포함되어 있으며, 부서의 위치에 따른 추가 시간은 없다. 하루의 시각은 0부터 시작하는 정수로 나타낸다. 담당자는 시각 0부터 일할 수 있고, 첫 번째 요청을 시작하기 전에는 정리 시간이 필요하지 않다. 마지막 요청이 끝난 뒤의 정리 시간이 얼마에 끝나는지는 배정 가능 여부에 영향을 주지 않는다. C가 0이면 한 요청이 끝나는 시각에 곧바로 다음 요청을 시작할 수 있다. 각 요청을 처리했을 때 얻는 실적은 모두 1로 같다. 작업 시간이 짧거나 특정 부서에서 보낸 요청이라고 해서 추가 실적을 얻지는 않는다. 시작 시각과 종료 시각이 모두 같은 요청이 여러 개 있어도 서로 다른 요청이지만, 담당자가 동시에 둘 이상의 작업을 수행할 수는 없다. 지원실은 처리하는 요청의 개수를 최대화하려 한다. 가능한 배정 방법이 여러 가지라면 어느 방법을 선택해도 된다. 요청의 번호나 실제 배정 순서는 출력하지 않고, 조건을 지키면서 처리할 수 있는 요청 개수의 최댓값만 구한다.

입력

첫째 줄에 요청의 수 N과 정리 시간 C가 공백으로 구분되어 주어진다.
다음 N개 줄에 각 요청의 시작 시각 s와 종료 시각 e가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 25,000, 0 ≤ C ≤ 1,000,000, 0 ≤ s < e ≤ 1,000,000이다. 요청은 임의의 순서로 주어진다.

출력

처리할 수 있는 요청 개수의 최댓값을 한 줄에 출력한다.

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

3

4 0
3 5
0 3
1 4
5 6

3

3 10
0 2
1 3
2 4

1

출처: Devin.KR 자체 제작