수조 해설 예약표

문제

한 수족관에서는 관람객이 신청한 시간에 맞추어 수조 앞에서 짧은 해설을 제공한다. 오늘 해설을 맡을 수 있는 직원은 한 명뿐이다. 여러 단체가 서로 다른 시간대의 해설을 신청했지만, 모든 신청을 받을 수는 없어 운영 담당자가 일부 신청을 확정하려 한다. 각 신청을 수락했을 때의 가치는 같으므로, 가능한 한 많은 신청을 확정하는 것이 목표이다. 신청에는 1번부터 N번까지 번호가 붙어 있으며, i번 신청의 해설 시작 시각은 S_i, 종료 시각은 E_i이다. 신청을 수락하면 직원은 시작 시각부터 종료 시각까지 해당 해설을 진행해야 한다. 신청 시각을 앞뒤로 옮기거나, 해설 시간을 줄이거나, 진행 중에 다른 신청으로 바꾸는 일은 허용되지 않는다. 신청 하나는 한 번만 수락할 수 있다. 직원은 해설 하나를 마친 뒤 안내 도구를 정리하고 다음 수조로 이동하는 데 정확히 C만큼의 시간이 필요하다. 따라서 종료 시각이 e인 신청 다음에 시작 시각이 s인 신청을 진행하려면 e+C ≤ s여야 한다. 두 값이 같으면 다음 해설을 바로 시작할 수 있다. C가 0이면 앞 해설이 끝나는 시각과 다음 해설이 시작하는 시각이 같아도 된다. 직원은 시각 0부터 준비되어 있으므로 첫 번째로 진행할 해설 앞에는 별도의 정리 시간이 필요하지 않다. 마지막 해설을 마친 뒤의 정리 시간에는 종료 시각 제한이 없다. 모든 신청의 시각은 같은 기준으로 표시하며, 신청이 입력되는 순서는 실제 진행 순서와 무관하다. 시작 시각과 종료 시각이 모두 같은 신청이 여러 개 있어도 각각 별개의 신청으로 취급하지만, 한 직원이 이들을 동시에 진행할 수는 없다. 운영 담당자는 확정한 신청을 시작 시각 순서대로 진행할 수 있어야 한다. 신청을 하나도 받지 않는 선택도 허용된다. 특히 신청이 처음부터 없으면 확정할 수 있는 개수는 0이다. 주어진 신청과 공통 정리 시간으로 진행 가능한 신청 개수의 최댓값을 구한다. 최대 개수를 만드는 예약표가 여러 개여도 예약표 자체는 출력하지 않고 그 개수만 출력한다.

입력

첫째 줄에 정수 N과 C가 공백으로 주어진다. 0 ≤ N ≤ 15,000, 0 ≤ C ≤ 999,999이다.
다음 N개 줄에 정수 S_i와 E_i가 공백으로 주어진다. 0 ≤ S_i < E_i ≤ 999,999이다. 중복된 신청이 허용된다.

출력

한 직원이 진행할 수 있는 신청 개수의 최댓값을 정수 하나로 출력한다.

6 2
0 3
3 5
5 7
8 10
9 11
13 14

4

3 0
1 4
1 4
4 6

2

0 5

0

출처: Devin.KR 자체 제작