Problem Description

An office has $N$ desks arranged from left to right, with some desks having telephones placed on them.

When the telephone on the $j$-th desk rings, the telephone on the $i$-th desk will also ring if and only if $|j-i| \le D$.

Given the arrangement of telephones, calculate the minimum number of additional telephones needed to ensure that the telephone on the last desk rings.

It is guaranteed that the first and last desks have telephones placed on them.

Input Format

The first line contains two positive integers $N$ and $D$, representing the number of desks and the maximum distance, respectively.

The second line contains $N$ integers $A_i$. If $A_i = 1$, it means there is a telephone on this desk; if $A_i = 0$, there is no telephone.

Output Format

A single line containing an integer representing the minimum number of additional telephones needed.

Sample Input and Output

Sample Input #1

4 1
1 0 1 1

Sample Output #1

1

Sample Input #2

5 2
1 0 0 0 1

Sample Output #2

1

Sample Input #3

8 2
1 1 0 0 1 0 0 1

Sample Output #3

2

Notes/Hints

[Sample Explanation #1]

Adding a telephone to the 2nd desk will make the telephone on the 4th desk ring.

[Sample Explanation #2]

Adding a telephone to the 3rd desk will make the telephone on the 5th desk ring.

[Sample Explanation #3]

Adding a telephone to the 4th and 7th desks will make the telephone on the 8th desk ring.

[Data Range]

For 50% of the data, $1 \le N \le 20$.

For 100% of the data, $1 \le D \le N \le 3 \times 10^5$.

[Notes]

This problem is scored according to the original COCI settings, with a maximum score of 80 points.

The problem is translated from COCI2016_2017 CONTEST #6 T2 TELEFONI.

见题面 Input 部分

见题面 Output 部分