호텔의 늦은 퇴실 요금

문제

한 호텔은 늦은 퇴실을 신청한 객실에 같은 계산 규칙으로 추가 요금을 부과한다. 오늘 정산할 객실은 모두 N개다. 각 객실의 퇴실 지연 시간은 원래 퇴실 시각보다 몇 분 늦게 퇴실했는지를 나타내는 0 이상의 정수로 기록되어 있다. 정시에 퇴실한 객실의 지연 시간은 0분이다. 호텔은 모든 객실에 G분의 무료 유예 시간을 제공한다. 지연 시간이 G분 이하인 객실에는 추가 요금을 부과하지 않는다. 지연 시간이 G분을 넘으면, 먼저 지연 시간에서 무료 유예 시간 G분을 뺀다. 이렇게 남은 시간을 유료 지연 시간이라고 한다. 유료 지연 시간은 B분 단위로 나누어 요금을 계산한다. 요금 단위 하나의 가격은 P원이다. 유료 지연 시간이 B분으로 정확히 나누어떨어지면 그 몫만큼 요금 단위를 적용한다. 나머지가 있으면 마지막의 짧은 시간도 요금 단위 하나로 계산한다. 예를 들어 유료 지연 시간이 B분보다 짧더라도 1분 이상이면 요금 단위 하나를 적용한다. 다만 한 객실에 부과하는 추가 요금은 C원을 넘을 수 없다. 계산된 요금이 C원보다 크면 해당 객실의 요금은 C원으로 정한다. 각 객실의 요금은 반드시 따로 계산한다. 여러 객실의 지연 시간을 합쳐서 유예 시간을 빼거나, 요금 단위를 함께 계산해서는 안 된다. 요금 상한 C원 역시 객실마다 각각 적용하며, C원이 P원의 배수일 필요는 없다. 기본 숙박비나 다른 비용은 이번 정산에 포함하지 않는다. 호텔이 오늘 받을 늦은 퇴실 추가 요금의 합계를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, G, B, P, C가 공백으로 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ G ≤ 1,000, 1 ≤ B ≤ 1,000, 1 ≤ P ≤ 100,000, 1 ≤ C ≤ 1,000,000이다.
둘째 줄에 각 객실의 지연 시간을 나타내는 정수 D_1, D_2, …, D_N이 공백으로 주어진다. 0 ≤ D_i ≤ 10,000이다.

출력

모든 객실에 부과하는 추가 요금의 합계를 원 단위의 정수 하나로 출력한다. 요금이 부과되는 객실이 없으면 0을 출력한다.

5 10 15 2000 5000
0 10 11 40 56

11000

3 20 5 700 900
0 19 20

0

4 0 10 600 1000
1 10 11 100

3200

출처: Devin.KR 자체 제작