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
ith floor there are
A_{i} 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 ≤ 10
^{9}, 1 ≤
P ≤ 10
^{9}, 1 ≤
T ≤ 10
^{9}). The second line contains the sequence of
N integers
A_{1},
A_{2},...,
A_{N} (0 ≤
A_{i} ≤ 10
^{9}). The sum of all
A_{i} does not exceed 10
^{9} 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
