기다릴 수 있는 충전

문제

전기차 충전소에 충전기가 한 대 설치되어 있다. 충전기는 시각 0부터 사용할 수 있으며, 한 번에 자동차 한 대만 충전할 수 있다. 이 충전소를 찾아오는 자동차 N대의 도착 시각과 필요한 충전 시간이 미리 주어진다. 모든 시각과 시간은 분 단위 정수이며, 날짜가 바뀌어도 시각을 0으로 되돌리지 않고 계속 증가시켜 표시한다. 자동차는 도착한 순서대로 충전 가능 여부를 결정한다. 도착 시각이 같은 자동차는 입력에 먼저 등장한 자동차부터 처리한다. 각 자동차를 처리할 때는 앞서 충전하기로 결정한 자동차들의 충전 일정을 모두 유지한다. 앞선 일정이 끝난 뒤 충전기를 사용할 수 있는 가장 이른 시각과 자신의 도착 시각 중 더 늦은 시각이 이 자동차의 충전 시작 예정 시각이다. 모든 자동차는 도착한 뒤 최대 W분까지 기다릴 수 있다. 충전 시작 예정 시각에서 도착 시각을 뺀 값이 W 이하라면 해당 자동차는 충전하기로 결정한다. 정확히 W분을 기다리는 경우도 충전한다. 충전하기로 결정한 자동차는 예정된 시각에 충전을 시작하고, 필요한 충전 시간만큼 충전기를 독점한다. 충전 도중에 다른 자동차를 위해 자리를 비우지 않는다. 기다려야 하는 시간이 W분보다 길다면 해당 자동차는 충전을 포기하고 즉시 다른 충전소로 떠난다. 이 자동차는 충전 일정에 아무런 영향을 주지 않는다. 뒤에 도착하는 자동차는 자신의 도착 시각과 필요한 충전 시간을 이용해 별도로 같은 규칙을 적용한다. 앞선 자동차가 포기했다는 이유로 함께 포기하지 않는다. 어떤 자동차의 충전 종료 시각과 다음 자동차의 충전 시작 시각이 같아도 된다. 충전 사이에 정리 시간은 필요하지 않다. 주어진 자동차를 모두 처리한 뒤, 충전하기로 결정한 자동차 수와 마지막 충전이 끝나는 시각을 구한다. 충전하기로 결정한 자동차가 하나도 없다면 마지막 종료 시각은 0으로 정한다.

입력

첫째 줄에 정수 N과 W가 주어진다. 1≤N≤20000, 0≤W≤1000000이다.
다음 N개 줄의 i번째 줄에 정수 t_i와 d_i가 주어진다. t_i는 도착 시각이며 0≤t_i≤1000000이다. d_i는 필요한 충전 시간이며 1≤d_i≤1000이다.
도착 시각은 감소하지 않는 순서로 주어진다. 즉, 모든 1≤i<N에 대해 t_i≤t_(i+1)이다.

출력

충전하기로 결정한 자동차 수와 마지막 충전 종료 시각을 공백으로 구분하여 한 줄에 출력한다. 충전한 자동차가 없다면 0 0을 출력한다.

5 3
0 5
1 2
2 2
6 4
6 1

3 11

4 0
2 3
2 1
5 2
8 1

3 9

3 4
0 4
0 2
0 1

2 6

출처: Devin.KR 자체 제작