충전 사이의 점검 시간

문제

한 전기차 충전소는 예약 전용 충전기 한 대를 운영한다. 하루 동안 여러 차량이 충전을 신청했으며, 각 신청에는 충전을 시작할 시각과 끝낼 시각이 정해져 있다. 충전소는 신청 중 일부를 승인하여 실제 예약표를 만들려 한다. 모든 차량의 신청을 승인할 필요는 없다. 신청 하나를 승인하면 그 차량은 신청한 시작 시각부터 종료 시각까지 충전기를 사용한다. 신청한 시각을 앞당기거나 늦추거나 충전 시간을 나누는 일은 허용되지 않는다. 충전기 한 대로 두 차량을 동시에 충전할 수 없으며, 충전이 끝난 뒤에는 다음 차량을 받기 전에 일정한 점검 시간이 필요하다. 점검에 필요한 시간은 모든 차량에 대해 같은 정수 G다. 어떤 차량의 충전 종료 시각이 E라면, 그다음 차량의 충전 시작 시각은 E + G 이상이어야 한다. 정확히 E + G에 시작하는 신청도 승인할 수 있다. 점검 중에는 차량을 충전할 수 없지만, 필요한 시간보다 더 오래 충전기를 비워 두는 것은 가능하다. 하루의 첫 번째 승인 차량은 이전 차량이 없으므로 시작 전에 점검 시간을 확보할 필요가 없다. 마지막 승인 차량의 충전이 끝난 뒤에는 뒤따르는 차량이 없으므로 추가 점검을 예약표에 넣을 필요가 없다. 따라서 마지막 종료 시각 뒤에 G만큼의 시간이 더 존재하는지는 확인하지 않는다. 충전소의 목표는 승인하는 신청의 개수를 최대화하는 것이다. 각 신청의 이용료나 충전량은 고려하지 않는다. 시작 시각과 종료 시각이 같은 두 신청이 있어도 서로 다른 신청이며, 각각 승인 여부를 결정한다. 최대 개수를 달성하는 예약표가 여러 개라면 그중 어느 것을 택해도 된다. 신청 목록과 점검 시간 G가 주어졌을 때 승인할 수 있는 신청 개수의 최댓값을 구한다. 신청이 하나도 없다면 승인할 수 있는 개수는 0이다.

입력

첫째 줄에 신청 수 N과 점검 시간 G가 공백으로 주어진다. N과 G는 정수이며 0 ≤ N ≤ 30,000, 0 ≤ G ≤ 1,000이다.
다음 N개 줄에 각 신청의 시작 시각 S_i와 종료 시각 E_i가 공백으로 주어진다. 모든 시각은 정수이며 0 ≤ S_i < E_i ≤ 100,000이다.
입력은 시각 순서로 정렬되어 있지 않을 수 있다.

출력

승인할 수 있는 신청 개수의 최댓값을 한 줄에 출력한다.

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

3

4 0
3 6
0 3
0 3
6 7

3

0 5

0

출처: Devin.KR 자체 제작