As a construction worker, you want to build a bamboo scaffold for an upcoming festival. There are specific requirements for the final scaffold, which will be part of a vertical, $2$-dimensional grid. $N+1$ vertical long bamboos are already established, so there are $N$ columns in between. Initially all columns are empty. Our task is to place exactly $H_ i$ horizontal short bamboos in the $i$th column, literally from the ground up.
You can carry at most $M$ short bamboos at a time. You will install the short bamboos in a number of rounds. In each round, you take at most $M$ short bamboos with you, and start anywhere on ground level.
You can only stand on a short bamboo that was built previously (or on ground level). Then you have two options:
Climb left, right or up if a short bamboo is already in place there
Place a short bamboo to the left, right or up if there is no short bamboo already placed
Note that you cannot go down while carrying short bamboos. You cannot place a short bamboo below you either.
Once you finish placing all the short bamboos in the current round, you go down to the ground level. You then take at most $M$ short bamboos with you and start another round from the ground level. This goes on until you have built the desired scaffold, with exactly $H_ i$ short bamboos in column $i$ for all $i$.
What is the minimum number of rounds you need?
The first line contains two integers, $N$ and $M$ ($1 \leq N \leq 100\, 000$, $1 \leq M \leq 10^9$). The second line contains $N$ integers $H_1, \dots , H_ N$ ($0 \leq H_ i \leq 100\, 000$).
Output an integer representing the minimum number of rounds.
Sample Input 1 | Sample Output 1 |
---|---|
3 4 2 1 5 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
5 10 2 1 2 1 2 |
3 |