세탁기 배정 장부

문제

한 세탁소는 자동 세탁기 K대를 사용한다. 세탁기에는 1번부터 K번까지 서로 다른 번호가 붙어 있다. 영업을 시작하는 시각을 0으로 정하며, 이 시각에는 모든 세탁기가 비어 있다. 오늘 처리할 세탁물 묶음 N개는 이미 접수 순서대로 정리되어 있다. 각 묶음의 세탁 시간은 양의 정수로 주어지며, 어느 세탁기에 넣더라도 같은 시간이 걸린다. 직원은 접수 순서대로 묶음을 하나씩 배정한다. 다음 묶음을 배정할 때는 현재까지 배정된 작업을 모두 마치는 시각이 가장 이른 세탁기를 고른다. 그 시각이 같은 세탁기가 여러 대라면 번호가 가장 작은 세탁기를 고른다. 아직 한 번도 작업을 배정받지 않은 세탁기는 작업을 마치는 시각이 0인 것으로 취급한다. 선택한 세탁기의 기존 작업 완료 시각이 S이고 새 묶음의 세탁 시간이 D라면, 새 묶음은 시각 S에 시작하여 시각 S+D에 완료된다. 직원이 묶음을 배정하는 데 드는 시간과 세탁물을 넣고 꺼내는 시간은 모두 0이다. 배정은 앞으로 수행할 작업을 예약하는 방식이므로, 앞선 묶음의 세탁이 실제로 끝날 때까지 기다렸다가 다음 배정을 결정하는 것은 아니다. 한 번 정한 배정은 나중에 바꾸지 않는다. 세탁소는 이 규칙대로 작성한 장부에서 세 가지 값을 확인하려 한다. 첫 번째는 모든 묶음의 세탁이 끝나는 시각이다. 두 번째는 각 묶음의 완료 시각을 모두 더한 값이다. 세 번째는 접수 순서상 마지막 묶음이 배정된 세탁기의 번호다. 마지막 묶음이 전체 작업 중 가장 늦게 완료되는 묶음이라는 보장은 없다. 세 가지 값을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 K가 주어진다. 1 ≤ N ≤ 20,000, 1 ≤ K ≤ 20,000이다.
둘째 줄에 접수 순서대로 각 묶음의 세탁 시간을 나타내는 정수 D_1, D_2, …, D_N이 주어진다. 모든 i에 대해 1 ≤ D_i ≤ 999이다.

출력

첫째 줄에 모든 묶음의 세탁이 끝나는 시각을 출력한다. 둘째 줄에 N개 묶음 각각의 완료 시각을 모두 더한 값을 출력한다. 셋째 줄에 마지막 묶음이 배정된 세탁기의 번호를 출력한다. 모든 값은 정수로 출력한다.

5 2
4 2 3 1 2

7
23
1

3 5
7 7 1

7
15
3

4 1
2 1 3 2

8
19
1

출처: Devin.KR 자체 제작