편의점 계산대 배정

문제

편의점에 계산대가 K개 있고 번호는 1번부터 K번까지다. 오늘 N명의 손님이 계산을 하러 온다. i번 손님은 시각 a_i에 계산대 앞에 도착하고, 계산에 정확히 s_i의 시간이 걸린다. 손님의 번호는 입력 순서대로 1번부터 N번까지이며, 도착 시각 순서로 주어지는 것은 아니다. 계산대는 한 번에 한 손님만 처리하고, 한 번 시작한 계산은 중간에 끊지 않는다. 계산대 배정은 다음 규칙을 따른다. 어떤 시각에 비어 있는 계산대가 하나 이상 있고 도착해서 기다리는 손님이 한 명 이상 있다면, 그 시각에 계산이 시작된다. 기다리는 손님 중 계산 시간 s가 가장 짧은 손님이 선택되고, s가 같으면 손님 번호가 작은 쪽이 선택된다. 비어 있는 계산대가 여러 개이면 번호가 가장 작은 계산대가 그 손님을 맡는다. 같은 시각에 계산이 끝나는 계산대는 그 시각에 비어 있는 것으로 보고, 같은 시각에 도착한 손님은 그 시각에 기다리는 것으로 본다. 따라서 도착한 즉시 빈 계산대가 있으면 대기 시간 없이 시작한다. 한 시각에 여러 손님의 계산이 시작될 수 있으며, 위 규칙을 한 명씩 반복해서 적용한다. 손님의 대기 시간은 (계산 시작 시각) - a_i이다. 모든 손님의 대기 시간의 합, 마지막 계산이 끝나는 시각, 그리고 대기 시간이 가장 긴 손님의 번호를 구하라. 대기 시간이 가장 긴 손님이 여럿이면 번호가 가장 작은 손님을 출력한다.

입력

첫 줄에 손님 수 N과 계산대 수 K가 공백으로 구분되어 주어진다(1 ≤ N ≤ 200000, 1 ≤ K ≤ N). 이어서 N개의 줄에 i번 손님의 a_i와 s_i가 공백으로 구분되어 주어진다(0 ≤ a_i ≤ 10^9, 1 ≤ s_i ≤ 10000). 모든 값은 정수다.

출력

한 줄에 대기 시간의 합, 마지막 계산이 끝나는 시각, 대기 시간이 가장 긴 손님의 번호를 공백으로 구분해 출력한다.

4 2
0 5
1 3
2 1
2 2

5 7 4

3 1
0 3
0 3
0 1

5 7 2

2 3
100 7
100 7

0 107 1

출처: Devin.KR 자체 제작