농장의 빗물 물통

문제

한 농장은 빗물을 모으는 물통 하나를 이용해 작은 재배 구역에 물을 준다. 물통에 저장할 수 있는 물의 양에는 한계가 있으며, 농장에서는 앞으로 N일 동안 매일 같은 규칙으로 물통을 관리한다. 물의 양은 모두 리터 단위의 정수로 다룬다. 관찰을 시작하기 직전에는 물통에 S리터가 들어 있다. 하루의 작업은 두 단계로 진행한다. 먼저 그날 모은 빗물을 모두 물통에 붓는다. 물통에 원래 있던 물과 새로 부은 빗물의 합이 물통 용량 C리터를 넘으면, 넘친 물은 즉시 밖으로 흘러나가고 물통에는 정확히 C리터만 남는다. 밖으로 흘러나간 물은 따로 보관하지 않으며, 그날 물주기나 이후 날짜에 사용할 수 없다. 빗물을 붓고 넘친 물을 처리한 다음에는 재배 구역에 물을 줄 수 있는지 확인한다. 한 번 물을 줄 때는 정확히 W리터가 필요하다. 이때 물통에 W리터 이상이 있으면 물주기를 한 번 실행하고 물통에서 W리터를 뺀다. W리터보다 적으면 그날의 물주기는 실행하지 않고 물을 그대로 남긴다. 물이 부족하다고 남은 물을 일부만 사용하는 일은 없다. 하루에 물주기는 최대 한 번만 실행한다. 한 번 물을 준 뒤에도 W리터 이상이 남아 있더라도 같은 날 다시 물을 주지 않는다. 물주기를 마치거나 건너뛴 뒤 남은 물은 다음 날로 그대로 이어지며, 증발이나 누수는 없다고 가정한다. 빗물을 모으는 단계가 물주기보다 먼저라는 점에 유의해야 한다. N일 동안 모을 빗물의 양이 날짜 순서대로 주어진다. 모든 날짜의 작업을 마쳤을 때 물주기를 실행한 날의 수와 물통에 남은 물의 양을 구하는 프로그램을 작성한다. 물주기를 한 번도 실행하지 못할 수도 있으며, 마지막에 남은 물이 0리터일 수도 있다.

입력

첫째 줄에 정수 N, C, W, S가 공백으로 구분되어 주어진다. N은 관찰할 날짜 수, C는 물통 용량, W는 한 번의 물주기에 필요한 물의 양, S는 시작 직전 물의 양이다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 1 ≤ W ≤ C, 0 ≤ S ≤ C이다.
둘째 줄에 각 날짜에 모을 빗물의 양을 나타내는 정수 R_1, R_2, …, R_N이 공백으로 구분되어 주어진다. 모든 i에 대해 0 ≤ R_i ≤ 1,000이다.

출력

물주기를 실행한 날의 수와 N일째 작업이 끝난 뒤 물통에 남은 물의 양을 공백으로 구분하여 한 줄에 출력한다. 물주기를 실행한 날이 없으면 첫 번째 값으로 0을 출력한다.

5 10 6 2
3 8 0 2 7

3 1

3 8 5 0
1 1 2

0 4

2 10 3 10
100 0

2 4

출처: Devin.KR 자체 제작