창고의 저녁 출고

문제

한 물류 창고는 같은 크기의 운반 상자를 보관한다. 창고 담당자는 매일 아침 새 상자를 받고, 그날 저녁 정해진 수만큼 상자를 출고한다. 첫날 아침에 새 상자가 들어오기 전에는 창고가 비어 있다. 전날 저녁 출고가 끝난 뒤 남은 상자는 다음 날 아침까지 그대로 보관한다. 창고에는 상자를 정리하여 보관할 수 있는 기준 수량 C가 있다. 아침 입고 직후의 전체 상자 수가 C보다 많으면, 담당자는 그날을 혼잡한 날로 기록한다. 전체 상자 수가 정확히 C인 날은 혼잡한 날이 아니다. C는 입고를 제한하는 수량이 아니므로, 기준을 넘는 상자가 들어와도 모든 상자를 창고에 받는다. 혼잡 여부는 하루에 한 번, 아침 입고가 모두 끝난 직후에만 확인한다. 저녁에는 최대 K개의 상자를 출고한다. 그때 창고에 상자가 K개 이상 있으면 정확히 K개를 출고하고, K개보다 적으면 있는 상자를 모두 출고한다. 따라서 상자 수가 음수가 되는 일은 없다. 출고하지 못한 수량을 다음 날 추가로 출고하지는 않으며, 다음 날에도 최대 K개만 출고한다. 아침에 혼잡한 날로 기록되었다면 저녁 출고 후 상자 수가 줄어들어도 그 기록은 취소하지 않는다. 담당자는 연속된 N일 동안 아침에 들어오는 상자 수를 알고 있다. 이 기간의 혼잡한 날 수와 마지막 날 저녁 출고까지 끝난 뒤 창고에 남은 상자 수를 구하려 한다. 날짜는 입력에 주어진 순서대로 진행되며, 입고와 출고 사이에 다른 상자 이동은 없다. 두 값을 계산하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, C, K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 1 ≤ K ≤ 1,000이다. 둘째 줄에 각 날 아침의 입고량을 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 1,000이다.

출력

혼잡한 날 수와 마지막 날 저녁 출고 후 남은 상자 수를 이 순서대로 공백 하나로 구분하여 출력한다. 혼잡한 날이 없으면 첫 번째 값으로 0을 출력한다.

4 7 3
5 6 0 8

2 7

3 4 5
4 0 2

0 0

1 2 1
5

1 4

출처: Devin.KR 자체 제작