학원의 보충 수업 편성

문제

한 학원은 강의실 하나에서 보충 수업 N개를 차례대로 진행하려 한다. 수업 순서는 이미 정해져 있으며, 순서를 바꾸거나 수업을 둘로 나누어 진행할 수 없다. 매일 강의실을 사용할 수 있는 시간은 하루 시작부터 L분 동안이다. 첫날의 첫 수업은 하루 시작 시각인 0분에 시작한다. 다음 날로 넘어갈 때도 그날의 첫 수업은 0분에 시작한다. 학생과 강사는 같은 날 수업을 K개 진행할 때마다 다음 수업 전에 B분 동안 쉬어야 한다. 구체적으로, 현재 날짜에 이미 끝낸 수업 수가 양의 K의 배수라면 같은 날 다음 수업을 시작하기 전에 휴식이 필요하다. 그 밖의 경우에는 휴식 없이 다음 수업을 바로 시작한다. 휴식 규칙은 날짜마다 새로 적용하므로 전날에 몇 개의 수업을 했는지는 다음 날에 영향을 주지 않는다. 다음 수업을 편성할 때는 먼저 현재 날짜에 필요한 휴식 시간과 그 수업 시간을 모두 더해 본다. 이를 현재까지 사용한 시간에 더한 값이 L 이하라면 필요한 휴식을 진행한 뒤 같은 날 수업을 진행한다. 정확히 L분에 끝나는 수업도 같은 날에 진행할 수 있다. 합이 L보다 크면 그 수업은 다음 날의 첫 수업으로 옮긴다. 이때 현재 날짜에 예정했던 휴식은 실제로 진행하지 않으며 휴식 횟수에도 포함하지 않는다. 시간이 남더라도 다른 수업을 먼저 넣지는 않는다. 마지막 수업이 끝난 뒤에는 휴식을 진행하지 않는다. 따라서 K번째 수업을 마쳤다는 이유만으로 휴식을 추가하거나 날짜를 늘리지 않는다. 각 수업의 길이는 L 이하이므로 다음 날로 옮긴 수업은 반드시 그날의 첫 수업으로 진행할 수 있다. 모든 수업을 위 규칙에 따라 편성했을 때 사용한 날짜 수, 마지막 날의 수업 종료 시각, 실제로 진행한 휴식 횟수를 구해야 한다. 종료 시각은 마지막 날의 시작부터 지난 분 수이며, 날짜 사이에 흐른 시간은 포함하지 않는다.

입력

첫째 줄에 N, L, K, B가 공백으로 구분되어 주어진다. 모두 정수이며 1 ≤ N ≤ 100,000, 1 ≤ L ≤ 1,000,000, 1 ≤ K ≤ 100,000, 1 ≤ B ≤ L이다.
둘째 줄에 순서대로 각 수업의 길이 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 L 이하의 정수이다.

출력

사용한 날짜 수, 마지막 날의 수업 종료 시각, 실제로 진행한 휴식 횟수를 공백으로 구분하여 한 줄에 출력한다.

5 12 2 3
4 3 2 5 4

2 9 1

3 10 1 4
6 5 5

3 5 0

2 10 2 3
4 6

1 10 0

출처: Devin.KR 자체 제작