게임 서버의 분별 대기 기록

문제

한 게임 서버는 이용자가 보낸 보상 수령 요청을 모아서 처리한다. 관리자는 서버를 관찰하는 시간을 1번부터 N번까지의 구간으로 나누었다. 각 구간의 길이는 1분이며, i번 구간이 시작할 때 새로운 요청 A_i개가 한꺼번에 도착한다. 관찰을 시작하기 전에는 기다리는 요청이 하나도 없다. 모든 요청은 같은 양의 작업을 필요로 하므로 요청의 종류나 도착한 이용자는 구분하지 않는다. 서버는 매 구간마다 최대 C개의 요청을 처리할 수 있다. 한 구간이 시작되면 먼저 그 구간에 도착한 요청을 이전 구간에서 남은 요청에 더한다. 그다음 기다리는 요청이 C개 이상이면 정확히 C개를 처리하고, C개보다 적으면 기다리는 요청을 전부 처리한다. 처리된 요청은 대기 목록에서 사라지고, 처리되지 않은 요청만 다음 구간으로 넘어간다. 한 구간에서 사용하지 않은 처리 능력은 다음 구간으로 넘길 수 없다. 예를 들어 어떤 구간에 기다리는 요청이 하나도 없었다고 해도, 다음 구간에서 처리할 수 있는 요청 수는 여전히 최대 C개이다. 반대로 요청이 많이 쌓여 있어도 한 구간에서 C개를 초과하여 처리할 수 없다. 새로운 요청이 0개인 구간에도 이전부터 기다리던 요청은 같은 규칙으로 처리한다. 관리자는 관찰한 N개 구간 동안 실제로 처리한 요청의 총개수와, 각 구간이 끝난 직후 남아 있던 요청 수의 최댓값을 알고 싶다. 최댓값을 구할 때에는 해당 구간의 처리 작업까지 마친 뒤의 대기 요청 수만 사용한다. 구간 시작 직후 새 요청을 더했을 때의 수는 기록 대상이 아니다. 최대 대기 요청 수가 양수라면 그 수가 처음 기록된 구간 번호도 함께 구한다. 같은 최댓값이 여러 번 기록되면 가장 작은 구간 번호를 선택한다. 모든 구간이 끝날 때 대기 요청이 0개였다면 최대 대기 요청 수와 구간 번호를 모두 0으로 기록한다. N번 구간 이후에 남은 요청은 추가로 처리하지 않는다.

입력

첫째 줄에 정수 N과 C가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000이고 1 ≤ C ≤ 100이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 i에 대하여 0 ≤ A_i ≤ 100이다.

출력

관찰 중 처리한 요청의 총개수, 구간 종료 직후의 최대 대기 요청 수, 그 최댓값이 처음 기록된 구간 번호를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 최대 대기 요청 수가 0이면 구간 번호도 0으로 출력한다.

5 4
7 0 9 2 0

18 5 3

4 5
0 5 2 0

7 0 0

4 3
5 3 0 5

11 2 1

출처: Devin.KR 자체 제작