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 ≤ 10
9, 1 ≤
P ≤ 10
9, 1 ≤
T ≤ 10
9). The second line contains the sequence of
N integers
A1,
A2,...,
AN (0 ≤
Ai ≤ 10
9). The sum of all
Ai 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
|