[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, 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 (1 ≤ H ≤ 50). The second line contains N-1 integers D_i, representing the distances between pairs of consecutive domino pieces, in the order given by the line (1 ≤ D_i ≤ 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