헬스장 기구 대기열

문제

헬스장에 같은 종류의 러닝머신이 K대 있고, 1번부터 K번까지 번호가 붙어 있다. 회원 N명이 도착하는 순서대로 주어지며, i번째 회원은 도착 시각 t_i, 이용 시간 d_i, 인내 시간 p_i를 가진다. 도착 시각은 t_1 ≤ t_2 ≤ ... ≤ t_N 이며, 도착 시각이 같으면 입력 순서대로 처리한다. 기구는 사용이 끝난 뒤 청소에 C만큼의 시간이 더 필요하며, 청소가 끝나야 다음 회원이 쓸 수 있다. 즉 시각 s에 사용을 시작한 기구는 시각 s + d_i + C 에 비로소 비게 된다. 회원이 도착했을 때 다음과 같이 행동한다. 먼저 시각 t_i 이하에 비는(비어 있는) 기구가 있으면, 그중 번호가 가장 작은 기구를 즉시 쓴다. 그런 기구가 없으면 모든 기구가 사용 중 또는 청소 중이므로, 가장 먼저 비는 기구(비는 시각이 같으면 번호가 작은 기구)를 기다린다. 이때 기다릴 시간, 즉 그 기구가 비는 시각 - t_i 가 p_i보다 크면 회원은 기다리지 않고 떠나며, 떠난 회원은 어떤 기구에도 영향을 주지 않는다. p_i 이하이면 기다렸다가 그 기구를 쓴다. 대기 중인 회원이 먼저 기구를 확보하므로 이후 도착하는 회원은 이미 배정된 기구를 가로챌 수 없다. 떠난 회원의 수, 기구를 쓴 회원들의 대기 시간 합, 대기 시간의 최댓값, 기구를 쓴 마지막 회원이 사용한 기구 번호를 구하는 프로그램을 작성하시오. 기구를 쓴 회원이 없으면 대기 시간 합과 최댓값은 0, 기구 번호는 0으로 한다.

입력

첫 줄에 N, K, C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 200,000, 0 ≤ C ≤ 10^9) 이어서 N개의 줄에 t_i, d_i, p_i가 공백으로 구분되어 주어진다. (0 ≤ t_i ≤ 10^9, 1 ≤ d_i ≤ 10^9, 0 ≤ p_i ≤ 10^9, 정수이며 t_i는 비내림차순)

출력

한 줄에 떠난 회원 수, 대기 시간 합, 대기 시간 최댓값, 마지막으로 기구를 쓴 회원의 기구 번호를 공백으로 구분하여 출력한다.

5 2 1
0 5 0
1 3 0
2 2 3
3 2 1
10 1 0

1 3 3 1

3 1 0
0 2 0
1 1 5
1 1 0

1 1 1 1

1 3 5
7 4 0

0 0 0 1

출처: Devin.KR 자체 제작