학원 인쇄기의 절전 모드

문제

한 학원은 수업 자료를 인쇄하는 인쇄기 한 대를 사용한다. 하루 동안 총 N개의 인쇄 요청이 들어오며, 각 요청에는 도착 시각 t와 인쇄할 장수 p가 적혀 있다. 시각은 하루의 기준 시점부터 지난 시간을 나타내는 정수이고, 시간의 단위는 분이다. 인쇄기는 한 장을 인쇄하는 데 정확히 1분이 걸리며, 한 요청의 인쇄를 시작하면 그 요청의 모든 장을 연속해서 인쇄한다. 요청은 입력된 순서대로 처리한다. 입력에서는 도착 시각이 빠른 요청이 먼저 주어지며, 도착 시각이 같은 요청도 입력에서 먼저 나온 요청을 먼저 처리한다. 인쇄기가 다른 요청을 처리하고 있을 때 도착한 요청은 순서를 기다린다. 진행 중인 인쇄나 준비 작업은 새 요청이 도착해도 중단하지 않는다. 인쇄기는 처음에 절전 모드에 있다. 절전 모드에서 요청을 처리하려면 먼저 W분 동안 준비 작업을 해야 하며, 준비 작업이 끝난 직후 인쇄를 시작한다. 첫 요청은 자신의 도착 시각에 준비 작업을 시작한다. 준비 작업 중에는 어떤 요청의 종이도 인쇄되지 않는다. 어떤 요청의 인쇄가 끝났을 때 이미 도착해 기다리는 요청이 있으면, 다음 요청의 인쇄를 즉시 시작한다. 기다리는 요청이 없다면 인쇄기는 켜진 상태로 대기한다. 마지막 인쇄 종료 시각부터 K분 동안 새 요청이 도착하지 않으면 절전 모드로 바뀐다. 다음 요청이 마지막 종료 시각보다 K분 이상 늦게 도착하면 준비 작업을 다시 해야 한다. 정확히 K분 뒤에 도착하는 경우에도 준비 작업이 필요하다. K분보다 일찍 도착하면 준비 작업 없이 도착 즉시 인쇄한다. 모든 요청을 처리했을 때 마지막 요청의 인쇄가 끝나는 시각과, 하루 동안 실행한 준비 작업의 횟수를 구한다. 마지막 인쇄가 끝난 뒤 절전 모드로 바뀌는 시각은 답에 영향을 주지 않는다.

입력

첫째 줄에 정수 N, K, W가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 40,000이고 1 ≤ K, W ≤ 9이다.
다음 N개 줄에는 각 요청의 정수 t와 p가 공백으로 구분되어 주어진다. 0 ≤ t ≤ 9,999이고 1 ≤ p ≤ 9이다. 요청의 도착 시각은 입력 순서대로 감소하지 않는다.

출력

마지막 요청의 인쇄 종료 시각과 준비 작업 횟수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 두 값은 모두 정수이다.

4 3 2
0 2
1 1
8 2
10 1

13 2

2 3 2
5 1
11 1

14 2

3 1 1
0 1
0 2
0 3

7 1

출처: Devin.KR 자체 제작