Pipe Processing Problem

Facer is a part‐time worker in a factory and faces the following challenge: There are \(N\) steel pipes with lengths \(a_i\). A pipe processor machine can process \(k\) length of pipe per second. Facer needs to feed the pipes into the machine in order. However, the machine has a maximum waiting capacity of \(h\); that is, the total length of pipes that have been inserted (but not yet processed) cannot exceed \(h\) (note that \(a_i \le h\) for every \(i\)). Also, Facer can only insert a pipe at an integer second. Determine the minimum time required for Facer to process all the pipes.

Note: The machine processes continuously at a rate of \(k\) per second. At every integer second, Facer checks whether he can feed the next pipe (or multiple pipes) as long as the total length in the machine does not exceed \(h\). If the next pipe cannot be inserted immediately, Facer must wait for the machine to process enough length to create the necessary capacity.

inputFormat

The first line contains three integers: \(N\), \(h\), and \(k\) — the number of pipes, the maximum waiting length, and the processing rate (length per second), respectively.

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\), where \(a_i\) is the length of the \(i\)-th pipe.

outputFormat

Output a single integer — the minimum number of seconds required to process all pipes.

sample

3 5 3
4 3 1

3