|Codeforces Round #355 (Div. 2)|
Vanya smashes potato in a vertical food processor. At each moment of time the height of the potato in the processor doesn't exceed h and the processor smashes k centimeters of potato each second. If there are less than k centimeters remaining, than during this second processor smashes all the remaining potato.
Vanya has n pieces of potato, the height of the i-th piece is equal to a i. He puts them in the food processor one by one starting from the piece number 1 and finishing with piece number n. Formally, each second the following happens:
Provided the information about the parameter of the food processor and the size of each potato in a row, compute how long will it take for all the potato to become smashed.
The first line of the input contains integers n, h and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109) — the number of pieces of potato, the height of the food processor and the amount of potato being smashed each second, respectively.
The second line contains n integers a i (1 ≤ a i ≤ h) — the heights of the pieces.
Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.
5 6 3
5 4 3 2 1
5 6 3
5 5 5 5 5
5 6 3
1 2 1 1 1
Consider the first sample.
In the second sample, Vanya puts the piece of height 5 inside and waits for 2 seconds while it is completely smashed. Then he repeats the same process for 4 other pieces. The total time is equal to 2·5 = 10 seconds.
In the third sample, Vanya simply puts all the potato inside the processor and waits 2 seconds.