급수 수레의 남은 물컵

문제

마라톤 대회의 급수 담당자는 물컵을 싣는 수레를 끌고 정해진 순서대로 N개의 급수 지점을 방문한다. 수레에는 물컵을 최대 C개까지 실을 수 있으며, 첫 번째 지점에 도착하기 전에는 물컵 C개가 실려 있다. 각 지점에서는 선수들이 요청한 물컵을 나누어 준 뒤, 그 지점에 준비된 물컵을 수레에 보충한다. 지점 i에서 요청한 물컵의 수는 A_i개다. 담당자는 수레에 물컵이 충분하면 요청한 수만큼 나누어 준다. 부족하면 수레에 남은 물컵을 모두 나누어 주고, 나누어 주지 못한 수를 기록한다. 이때 부족했던 요청은 그 지점에서 끝난 것으로 처리한다. 다음 지점에서 물컵을 더 나누어 주어 이전 지점의 부족분을 채우지는 않는다. 물컵을 나누어 준 직후에는 해당 지점에 준비된 물컵 R개를 수레에 싣는다. 다만 수레의 물컵 수가 C개를 넘을 수는 없다. 빈자리가 R개보다 적으면 빈자리만큼만 싣고, 나머지는 그 지점에 남긴다. 보충에 사용하는 물컵은 각 지점에 따로 준비되어 있으므로 앞 지점에서 남긴 물컵 수는 뒤 지점에 영향을 주지 않는다. 요청한 물컵이 0개인 지점에서도 같은 보충 절차를 진행한다. 마지막 지점에서도 물컵을 나누어 준 다음 보충까지 마친다. 따라서 마지막으로 남은 물컵 수는 마지막 지점의 보충이 끝난 직후를 기준으로 한다. 모든 지점에서 나누어 주지 못한 물컵 수의 합과 마지막으로 수레에 남은 물컵 수를 구하는 프로그램을 작성한다. 부족한 물컵이 한 개도 없으면 부족한 물컵 수의 합은 0이다.

입력

첫째 줄에 정수 N, C, R이 공백으로 구분되어 주어진다. N은 급수 지점의 수, C는 수레에 실을 수 있는 물컵의 최대 개수, R은 각 지점에서 보충을 시도하는 물컵의 수다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 0 ≤ R ≤ C다.
둘째 줄에 정수 A_1, A_2, …, A_N이 방문 순서대로 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ A_i ≤ 1,000이다.

출력

모든 지점에서 나누어 주지 못한 물컵 수의 합과 마지막 지점에서 보충까지 마친 뒤 수레에 남은 물컵 수를 순서대로 한 줄에 공백으로 구분하여 출력한다. 두 값은 모두 정수로 출력한다.

4 5 2
3 6 1 5

4 2

3 4 0
0 2 1

0 1

1 1 1
3

2 1

출처: Devin.KR 자체 제작