영화관의 해설 수신기

문제

한 영화관은 관객이 음성 해설을 들을 수 있도록 휴대용 수신기를 빌려준다. 오늘 수신기를 예약한 관객은 N명이며, 각 관객은 정해진 시각에 수신기 한 대를 받아 정해진 시각에 반납한다. 영화관은 예약한 모든 관객이 기다리지 않고 수신기를 받을 수 있도록 준비해야 한다. 수신기는 모두 같은 기능을 가지며, 한 관객이 사용 중인 수신기를 다른 관객에게 빌려줄 수는 없다. 관객 i는 시각 S_i에 수신기를 받고 시각 E_i에 반납한다. 시각은 영업 시작 이후 지난 분을 나타내는 정수다. 수신기를 반납받으면 충전과 점검에 정확히 C분이 걸린다. 따라서 이 수신기를 다음 관객에게 줄 수 있는 가장 이른 시각은 E_i + C다. 다음 관객의 수령 시각이 이 값과 같아도 같은 수신기를 사용할 수 있다. C가 0이라면 반납한 시각에 즉시 다시 빌려줄 수 있다. 예약표는 관객 번호 순서로 작성되어 있으므로 입력된 수령 시각이 오름차순이라는 보장은 없다. 여러 관객이 같은 시각에 수신기를 받을 수도 있다. 이 경우에도 각 관객에게 서로 다른 수신기 한 대씩을 제공해야 한다. 반납과 점검이 끝난 수신기가 같은 시각에 여러 대 생기면 그중 어느 것을 빌려주어도 된다. 특정 수신기나 관객 번호를 우선하는 규칙은 없다. 영업 시작 시각에는 준비한 수신기가 모두 사용 가능한 상태다. 예약 시각을 바꾸거나 예약을 취소할 수 없으며, 모든 관객에게 필요한 시간 동안 수신기를 제공해야 한다. 예약표와 점검 시간 C가 주어질 때, 조건을 만족하기 위해 영화관이 준비해야 하는 수신기의 최소 대수를 구하는 프로그램을 작성한다. 실제 수신기 배정 내역은 출력하지 않는다.

입력

첫째 줄에 두 정수 N과 C가 공백으로 구분되어 주어진다.
다음 N개의 줄 중 i번째 줄에 두 정수 S_i와 E_i가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 20,000, 0 ≤ C ≤ 1,000이며, 모든 i에 대해 0 ≤ S_i < E_i ≤ 1,000,000이다.

출력

필요한 수신기의 최소 대수를 정수 하나로 출력한다.

4 2
0 3
5 7
3 4
9 10

2

3 0
8 10
0 4
4 8

1

4 1
2 5
2 3
2 7
4 6

3

출처: Devin.KR 자체 제작