379. Elevator

Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



There is only one elevator in the tall building with N floors. The parking for this building is at the basement floor which is located under the first floor. All floors are enumerated from 1 to N, growing up. At i-th floor there are Ai people who wish to descend from the floor to parking. You know that the elevator is unable to carry more than C people at any time. Descending or ascending one floor takes P seconds. Your task is to find the maximum possible number of people the elevator may deliver to parking within T seconds of operation, if it is located at the parking in the beginning. You may assume that stopping at a stage to load or unload people is done instantly.

Input
In the first line of input file there are four integers N, C, P, T (1 ≤ N ≤ 100, 1 ≤ C ≤ 109, 1 ≤ P ≤ 109, 1 ≤ T ≤ 109). The second line contains the sequence of N integers A1, A2,..., AN (0 ≤ Ai ≤ 109). The sum of all Ai does not exceed 109 too.

Output
Output the maximum possible number of people who can reach the parking.

Example(s)
sample input
sample output
4 5 2 15
0 1 2 3
3

sample input
sample output
4 5 2 18
0 1 2 3
5

sample input
sample output
3 2 1 9
1 1 1
3




Online Contester Team © 2002 - 2010. All rights reserved.