급수대의 빈자리

문제

마라톤 대회의 급수 구역에는 1번부터 K번까지 번호가 붙은 급수대가 있다. 각 급수대에서는 한 번에 선수 한 명만 물을 받을 수 있다. 선수는 급수 구역에 도착하면 안내 규칙에 따라 급수대를 배정받으며, 배정된 급수대에서 필요한 시간 동안 머문 뒤 떠난다. 모든 급수대는 시각 0부터 사용할 수 있다. 선수는 입력에 나타나는 순서대로 1번부터 N번까지 번호가 붙는다. i번 선수의 도착 시각은 A_i이고, 물을 받는 데 필요한 시간은 B_i이다. 도착 시각은 감소하지 않는 순서로 주어진다. 도착 시각이 같은 선수들은 번호가 작은 선수부터 처리한다. 앞선 선수의 배정은 뒤에 처리하는 선수보다 항상 먼저 확정된다. 선수를 처리할 때, 도착 시각에 비어 있는 급수대가 하나 이상이면 그중 번호가 가장 작은 급수대를 배정한다. 비어 있는 급수대가 없다면 가장 먼저 사용이 끝나는 급수대를 배정한다. 가장 먼저 사용이 끝나는 급수대가 여러 개이면 번호가 가장 작은 급수대를 고른다. 이 경우 선수는 그 급수대가 빌 때까지 기다린다. 배정이 끝난 선수의 사용 구간은 즉시 예약되므로, 다음 선수는 그 예약까지 반영하여 급수대를 선택한다. 시각 t에 사용이 끝난 급수대는 시각 t에 도착하거나 사용을 시작하는 선수에게 바로 배정할 수 있다. 선수의 대기 시간은 사용 시작 시각에서 도착 시각을 뺀 값이다. 모든 선수의 대기 시간 합, 마지막 사용 종료 시각, 그 시각에 사용을 마친 선수 중 번호가 가장 작은 선수를 구한다. 선수는 반드시 한 명 이상이며, 이동 시간은 고려하지 않는다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ K ≤ 20,000이다.
다음 N개 줄의 i번째 줄에 정수 A_i와 B_i가 주어진다. 0 ≤ A_i ≤ 99,999, 1 ≤ B_i ≤ 99이며, A_i ≤ A_(i+1)이다.

출력

모든 선수의 대기 시간 합, 마지막 사용 종료 시각, 그 시각에 사용을 마친 선수 중 가장 작은 번호를 공백으로 구분하여 한 줄에 출력한다.

4 2
0 5
0 3
1 2
3 1

4 6 4

1 3
7 2

0 9 1

출처: Devin.KR 자체 제작