TAP2012E - Emma s Domino

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]

 

The domino effect is a phenomenon that occurs when in a line of
domino pieces, each standing on its smallest face, the first
piece from one of the line's ends falls in the direction of the
next piece. In turn, this second piece falls over the third one
in the line, and so on until the other end of the line is
reached, at which point every piece has fallen. Note that in
order to produce this effect, the distance between consecutive
pieces in the line must be lower or equal to their height.
Emma has very recently found out about the domino effect, and
she was immediately amazed by it. She spent all morning forming
a line with the N domino pieces that her brother Ezequiel gave
her, but just before she was going to make the first piece
fall, her grandma came to her home and took her to play in the
park. Ezequiel knows Emma has not taken into account the
distance between consecutive pieces when she formed her domino
line, and doesn't want to see her frustrated if all the pieces
do not fall after she pushes the first one. Thus, Ezequiel
wants to move some pieces from inside the line so that the
distance between consecutive pieces is always lower or equal to
their height H. Because he doesn't want Emma to find out that
he has moved some of the pieces, que will leave the first and
last pieces where they are, and he would also like to move as
few pieces as possible from inside the line. What is the
minimum number of pieces he must move?

The domino effect is a phenomenon that occurs when in a line of domino pieces, each standing on its smallest face, the first piece from one of the line's ends falls in the direction of the next piece. In turn, this second piece falls over the third one in the line, and so on until the other end of the line is reached, at which point every piece has fallen. Note that in order to produce this effect, the distance between consecutive pieces in the line must be lower or equal to their height.

Emma has very recently found out about the domino effect, and she was immediately amazed by it. She spent all morning forming a line with the N domino pieces that her brother Ezequiel gave her, but just before she was going to make the first piece fall, her grandma came to her home and took her to play in the park. Ezequiel knows Emma has not taken into account the distance between consecutive pieces when she formed her domino line, and doesn't want to see her frustrated if all the pieces do not fall after she pushes the first one. Thus, Ezequiel wants to move some pieces from inside the line so that the distance between consecutive pieces is always lower or equal to their height H. Because he doesn't want Emma to find out that he has moved some of the pieces, he will leave the first and last pieces where they are, and he would also like to move as few pieces as possible from inside the line. What is the minimum number of pieces he must move?

 

Input

Each test case is described using two lines. The first line contains two integer numbers N and H, indicating respectively the number of pieces in the line (3 ≤ N  1000) and their height ( H  50). The second line contains N-1 integers Di, representing the distances between pairs of consecutive domino pieces, in the order given by the line ( Di ≤ 100 for i = 1, 2, ..., N-1). The end of the input is signalled by a line containing two times the number -1.

 

Output

For each test case, you should print a line containing a single integer number, representing the minimum number of pieces that must be moved in order to have the distance between consecutive pieces always lower or equal to H. Note that the first and last pieces cannot be moved, and that the relative order between the the pieces cannot be changed. If it is impossible to achieve the desired result, print the number -1.

 

Example

Input:
8 3
2 4 4 1 4 3 2
10 2
1 2 2 2 2 2 2 2 3
5 2
2 2 2 2
5 3
1 6 2 4
-1 -1

Output:
3
8
0
-1

Added by:Fidel Schaposnik
Date:2012-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2012

hide comments
2017-05-29 23:14:08
Getting WA...can someone provide more test cases
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.