급식실의 묶음 보충

문제

학교 급식실에서는 점심에 사용할 밀봉 소스 컵을 보관한다. 소스 컵은 낱개로 받을 수 없고, 항상 K개가 들어 있는 묶음으로만 공급받는다. 묶음을 받으면 즉시 포장을 열어 그 안의 모든 컵을 재고에 넣는다. 컵의 종류는 모두 같으며, 남은 컵은 보관했다가 다음 날 사용할 수 있다. 보관 중에 컵이 줄어들거나 버려지는 일은 없다. 급식 담당자는 앞으로 N일 동안 사용할 컵의 수를 날짜 순서대로 알고 있다. 첫째 날 아침에는 재고가 0개다. 각 날짜의 아침에는 먼저 현재 재고와 그날 필요한 컵 수를 비교한다. 재고가 충분하면 새 묶음을 받지 않는다. 재고가 부족하면 그날 필요한 수를 채울 수 있을 때까지 묶음을 받되, 받는 묶음 수가 가능한 한 적도록 한다. 그 뒤 점심에 그날 필요한 컵을 정확히 사용하고, 남은 컵을 다음 날로 넘긴다. 예를 들어 현재 재고가 2개이고 그날 8개가 필요하며 한 묶음에 5개가 들어 있다면, 부족한 6개를 채우기 위해 두 묶음을 받는다. 점심에 8개를 사용한 뒤에는 4개가 남는다. 미리 다음 날의 수요를 고려하여 묶음을 더 받는 일은 없다. 같은 날에 여러 묶음을 받아도 묶음을 받은 날짜 수는 하루로 센다. 담당자는 N일 동안 받은 묶음의 총수, 묶음을 하나 이상 받은 날짜 수, 마지막 날 점심이 끝난 뒤 남은 컵 수를 알고 싶다. 주어진 절차를 그대로 적용하여 이 세 값을 구하는 프로그램을 작성한다. 필요한 컵 수가 0인 날에도 날짜는 지나가지만 컵을 사용하지 않는다. 모든 날의 필요량이 0이면 묶음을 전혀 받지 않으며 마지막 재고도 0이다. 필요한 만큼의 묶음은 언제나 공급받을 수 있으므로, 공급 부족으로 급식을 진행하지 못하는 경우는 없다.

입력

첫째 줄에 날짜 수 N과 한 묶음에 들어 있는 컵 수 K가 공백으로 구분되어 주어진다. N과 K는 정수다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 100)
둘째 줄에 날짜 순서대로 필요한 컵 수 D_1, D_2, ..., D_N이 주어진다. 각 값은 정수다. (0 ≤ D_i ≤ 9)

출력

받은 묶음의 총수, 묶음을 하나 이상 받은 날짜 수, 마지막 날 점심이 끝난 뒤 남은 컵 수를 공백으로 구분하여 한 줄에 출력한다. 묶음을 한 번도 받지 않았다면 세 값 모두 0을 출력한다.

5 4
3 0 5 2 1

3 3 1

4 7
0 0 0 0

0 0 0

3 3
8 1 0

3 1 0

출처: Devin.KR 자체 제작