Problem Description

Facer is a part-time worker in a factory, and this time he encounters a problem.

There are $N$ steel pipes, each with a length of $a_i$.

There is a steel pipe processing machine that can process $k$ units of length per second.

Facer needs to process these pipes in order.

However, the machine has a maximum waiting length of $h$, meaning the total length of pipes waiting to be processed (those already inserted into the machine but not yet processed) cannot exceed $h$ (guaranteed $a_i \le h$).

Facer can only insert pipes at integer seconds.

How long will it take Facer to finish processing all these pipes in the shortest time?

Input Format

The first line contains $N, H, K$, representing the number of steel pipes, the maximum waiting length, and the processing speed per second, respectively.

The next $N$ lines each contain a number representing the length of a steel pipe.

Pipes need to be processed in order.

Output Format

The shortest time required.

Sample Input and Output

Sample Input #1

1 5 3
5

Sample Output #1

2

Sample Input #2

5 6 3
5 4 3 2 1

Sample Output #2

5

Notes

Sample 1 Explanation: There is only 1 steel pipe, and the processing time is $\lfloor 5/3\rfloor = 2$.

Sample 2 Explanation:

• First second: Insert $5$, waiting length $5$, machine processes $3$, waiting length $2$.
• Second second: Insert $4$, waiting length $6$, machine processes $3$, waiting length $3$.
• Third second: Insert $3$, waiting length $6$, machine processes $3$, waiting length $3$.
• Fourth second: Insert $1,2$, waiting length $6$, machine processes $3$, waiting length $3$.
• Fifth second: No insertion, waiting length $3$, machine processes $3$, processing complete.

Constraints: $N \le 100000$, $h, a_i \le 10^9$.

This problem is by zhouyonglong.

见题面 Input 部分

见题面 Output 部分