Limits 1s, 512 MB

In the ICPC World Cup cricket match, Bangladesh won the toss and chose to field first. To secure a victory, Bangladesh needs to strategically break the partnerships at crucial moments to minimize the total runs scored by opponent.

The strategy is as follows,

Hathurusingha provided a threshold KK to Bangladeshi bowlers, instructed them to take a wicket when the sum of runs scored in exactly two consecutive balls exceed the given threshold KK.

Now, you are provided with the total number of balls NN, played in the first innings, along with the runs scored in each ball. Your task is to calculate the number of wickets taken by Bangladesh team if they play strategically.

Input

The first line contains two integers NN and KK — representing total number of balled played and threshold provided by Hathurusingha respectively.

The second line contains NN integers a0,a1,,an1,ana_0,a_1,…,a_{n−1}, a_n — representing the runs scored in each ball.

1N3501 \leq N \leq 350

1K121 \leq K \leq 12

0ai60 \leq a_i \leq 6

Output

A single integer representing the number of wickets taken by Bangladesh team if they play strategically.

Sample

InputOutput
10 4
0 1 0 2 6 1 2 0 4 1
3

Submit

Login to submit.

Statistics

92% Solution Ratio
esh.29Earliest, 5M ago
jahid2994Fastest, 0.0s
emon192002Lightest, 5.2 MB
user.4273Shortest, 230B
Toph uses cookies. By continuing you agree to our Cookie Policy.