Description

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

There are $N$ steel pipes, with the $i$-th pipe having length $a_i$.

There is a pipe processor that can process $K$ units of pipe length per second.

Facer needs to process these pipes in order.

The machine has a maximum waiting length $H$, meaning the total length of pipes waiting to be processed (already fed into the machine but not yet processed) cannot exceed $H$ (guaranteed that $a_i \le H$).

Facer can only feed pipes into the machine at integer seconds.

What is the minimum time for Facer to finish processing all the pipes?

Input Format

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

The next $N$ lines each contain one number, the length of a pipe.

The pipes must be processed in order.

Output Format

The minimum time.

1 5 3
5

2

5 6 3
5 4 3 2 1

5

Hint

Sample 1 explanation: There is only $1$ pipe, and the processing time is $\lceil 5/3 \rceil = 2$.

Sample 2 explanation:

• At the first second, feed $5$, waiting length is $5$. The machine processes $3$, waiting length becomes $2$.
• At the second second, feed $4$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$.
• At the third second, feed $3$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$.
• At the fourth second, feed $1, 2$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$.
• At the fifth second, feed nothing, waiting length is $3$. The machine processes $3$, and all pipes are finished.

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

Problem by zhouyonglong.

Translated by ChatGPT 5