Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Vanya and Food Processor

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVanya 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:

- If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.
- Processor smashes
*k*centimeters of potato (or just everything that is inside).

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.

Input

The first line of the input contains integers *n*, *h* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ *h* ≤ 10^{9}) — 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.

Output

Print a single integer — the number of seconds required to smash all the potatoes following the process described in the problem statement.

Examples

Input

5 6 3

5 4 3 2 1

Output

5

Input

5 6 3

5 5 5 5 5

Output

10

Input

5 6 3

1 2 1 1 1

Output

2

Note

Consider the first sample.

- First Vanya puts the piece of potato of height 5 into processor. At the end of the second there is only amount of height 2 remaining inside.
- Now Vanya puts the piece of potato of height 4. At the end of the second there is amount of height 3 remaining.
- Vanya puts the piece of height 3 inside and again there are only 3 centimeters remaining at the end of this second.
- Vanya finally puts the pieces of height 2 and 1 inside. At the end of the second the height of potato in the processor is equal to 3.
- During this second processor finally smashes all the remaining potato and the process finishes.

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/12/2020 02:09:04 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|