예약 구간의 진료 시작

문제

한 병원의 진료실에는 의사가 한 명 있으며, 하루 동안 N명의 예약을 처리한다. 시간은 운영 시작 시각을 0으로 하는 정수로 나타낸다. 예약에는 1번부터 N번까지 번호가 붙어 있고, 각 예약에는 길이가 L인 진료 시작 구간이 배정되어 있다. i번 예약의 구간은 (i-1)×L 이상 i×L 미만이다. 구간의 왼쪽 끝 시각에는 진료를 시작할 수 있지만, 오른쪽 끝 시각에는 시작할 수 없다. 각 예약자에 대해 병원에 도착한 시각 A_i와 필요한 진료 시간 D_i가 주어진다. 예약자는 도착한 뒤 자신의 예약이 처리될 때까지 병원에 머문다. 병원은 도착 순서와 관계없이 예약 번호가 작은 순서로 각 예약을 정확히 한 번 검토한다. 나중 번호의 예약자가 먼저 도착했더라도 앞선 번호의 예약보다 먼저 진료받지는 않는다. 의사는 시각 0부터 진료할 수 있다. i번 예약을 검토할 때에는 의사의 직전 진료 종료 시각, 해당 예약 구간의 왼쪽 끝 시각, 예약자의 도착 시각 중 가장 큰 값을 진료 시작 후보 시각으로 정한다. 아직 진행한 진료가 없다면 직전 진료 종료 시각은 0으로 본다. 후보 시각이 해당 구간의 오른쪽 끝보다 작으면 그 시각에 진료를 시작하고, 정확히 D_i만큼 지난 시각에 종료한다. 진료가 시작되었다면 종료 시각이 예약 구간을 벗어나도 중단하지 않는다. 후보 시각이 구간의 오른쪽 끝 이상이면 해당 예약은 취소된다. 취소된 예약은 이후에 다시 검토하지 않으며, 의사의 직전 진료 종료 시각도 바꾸지 않는다. 앞선 진료가 길어지면 여러 예약이 연속으로 취소될 수도 있다. 모든 예약을 검토한 뒤 실제로 진료한 예약의 개수와 마지막으로 진행한 진료의 종료 시각을 구한다. 실제 진료가 하나도 없으면 종료 시각으로 0을 사용한다.

입력

첫째 줄에 정수 N과 L이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ L ≤ 1,000이다.
다음 N개 줄 중 i번째 줄에 정수 A_i와 D_i가 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 1,000,000, 1 ≤ D_i ≤ 1,000이다. 도착 시각은 정렬되어 있지 않을 수 있다.

출력

실제로 진료한 예약의 개수와 마지막 진료의 종료 시각을 공백으로 구분하여 한 줄에 출력한다. 실제 진료가 하나도 없으면 0 0을 출력한다.

4 10
0 15
12 4
29 3
30 5

4 37

3 5
5 2
0 12
10 1

1 17

2 3
3 1
6 2

0 0

출처: Devin.KR 자체 제작