개장 시각의 충전 대기열

문제

새로 문을 여는 전기차 충전소에 차량들이 개장 전부터 한 줄로 기다리고 있다. 충전소에는 1번부터 M번까지 번호가 붙은 충전기가 있다. 개장 시각을 0이라고 할 때 모든 충전기는 시각 0부터 사용할 수 있으며, 기다리는 N대의 차량도 모두 시각 0에 충전을 시작할 준비가 되어 있다. 차량에는 대기열의 앞에서부터 1번부터 N번까지 번호를 붙인다. 충전소는 이 번호 순서대로 차량을 충전기에 배정한다. 각 차량을 배정할 때는 현재 배정된 충전을 모두 마치는 시각이 가장 이른 충전기를 선택한다. 그러한 충전기가 여러 개라면 번호가 가장 작은 충전기를 선택한다. 배정을 받은 차량은 선택된 충전기가 앞선 충전을 마치는 즉시 충전을 시작한다. 차량마다 필요한 충전 시간이 정해져 있다. 같은 차량의 충전 시간은 어느 충전기를 사용하더라도 같으며, 충전을 시작한 뒤에는 중단하거나 다른 충전기로 옮길 수 없다. 충전을 마친 차량은 즉시 자리를 비우고, 다음 차량이 연결되는 데 추가 시간은 들지 않는다. 차량 한 대가 충전하는 동안 해당 충전기는 다른 차량을 충전할 수 없다. 예를 들어 어떤 충전기가 시각 t까지 사용되도록 배정되어 있고 새로 배정할 차량의 충전 시간이 d라면, 그 차량은 시각 t에 시작하여 시각 t+d에 충전을 마친다. 아직 한 번도 배정되지 않은 충전기는 충전을 마치는 시각을 0으로 취급한다. 차량의 충전 시간이 짧다는 이유로 대기 순서를 바꾸지는 않는다. 운영자는 모든 차량의 충전이 끝나는 시각과 대기열의 마지막 차량이 사용할 충전기 번호를 알고 싶다. 주어진 배정 규칙을 모든 차량에 적용한 뒤 두 값을 구한다. 마지막 차량이 반드시 가장 늦게 충전을 마치는 차량인 것은 아니라는 점에 유의한다.

입력

첫째 줄에 차량 수 N과 충전기 수 M이 공백으로 구분되어 주어진다.
둘째 줄에 1번 차량부터 N번 차량까지의 충전 시간 D_1, D_2, …, D_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ M ≤ N ≤ 50,000, 1 ≤ D_i ≤ 9,999이다.

출력

모든 차량의 충전이 끝나는 시각과 N번 차량이 배정된 충전기 번호를 이 순서대로 공백으로 구분하여 출력한다.

5 2
5 2 4 1 3

9 1

3 3
9 1 2

9 3

4 2
3 3 2 2

5 2

출처: Devin.KR 자체 제작