수조별 급이 기록

문제

수족관에는 1번부터 N번까지 번호가 붙은 수조가 있다. 자동 급이 장치는 여러 수조를 돌며 먹이 투입을 요청하고, 관리 프로그램은 각 요청을 승인하거나 거절한다. 너무 짧은 간격으로 먹이가 들어가는 일을 막기 위해 같은 수조에서 승인된 두 요청 사이에는 적어도 C초의 간격이 있어야 한다. 각 요청에는 요청 시각 t와 대상 수조 번호 x가 적혀 있다. 시각은 기록 시작 순간을 0초로 하여 지난 시간을 나타낸다. 기록은 요청 시각이 감소하지 않는 순서로 주어진다. 시각이 같은 요청이 여러 개라면 입력에 먼저 등장한 요청부터 처리한다. 수조 번호가 작다는 이유로 처리 순서가 바뀌지는 않는다. 처음에는 모든 수조에 승인된 요청이 없다. 대상 수조에 이전에 승인된 요청이 없다면 현재 요청을 승인한다. 이전에 승인된 마지막 요청의 시각이 s라면 t-s가 C 이상일 때만 현재 요청을 승인한다. 정확히 C초가 지난 요청도 승인한다. 승인된 요청은 즉시 해당 수조의 마지막 승인 시각을 현재 시각으로 바꾼다. 거절된 요청은 마지막 승인 시각에 영향을 주지 않는다. 예를 들어 간격 기준이 5초인 수조에서 2초의 요청이 승인되었다면, 6초의 요청은 거절되고 7초의 요청은 승인될 수 있다. 서로 다른 수조의 기록은 영향을 주고받지 않는다. 같은 시각이라도 서로 다른 수조에서는 각각 요청이 승인될 수 있다. 모든 요청을 처리한 뒤 전체 승인 횟수와 전체 거절 횟수를 구한다. 이어서 승인 횟수가 가장 많은 수조의 번호와 그 수조의 승인 횟수를 구한다. 가장 많은 횟수가 같은 수조가 여러 개라면 번호가 가장 작은 수조를 선택한다. 요청이 한 번도 없으면 모든 수조의 승인 횟수가 0이므로 1번 수조를 선택한다.

입력

첫째 줄에 정수 N, M, C가 공백으로 주어진다. N은 수조 수, M은 요청 수, C는 최소 승인 간격이다. 1≤N≤10,000, 0≤M≤25,000, 1≤C≤1,000,000이다.
다음 M개 줄에 정수 t, x가 공백으로 주어진다. 0≤t≤1,000,000, 1≤x≤N이다. t는 입력 순서대로 감소하지 않는다.

출력

첫째 줄에 전체 승인 횟수와 전체 거절 횟수를 공백으로 출력한다. 둘째 줄에 선택한 수조 번호와 그 수조의 승인 횟수를 공백으로 출력한다. 모든 값은 정수로 출력한다.

3 7 5
0 2
0 2
3 1
5 2
7 1
8 1
8 3

5 2
1 2

4 0 9

0 0
1 0

2 4 3
1 2
3 2
4 2
4 1

3 1
2 2

출처: Devin.KR 자체 제작