Description

There are $N$ desks in an office arranged from left to right, and some desks have telephones.

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

You are given the current placement of telephones. Find the minimum number of telephones that need to be added so that the telephone on the last desk will ring.

It is guaranteed that there is a telephone on the first desk and on the last desk.

Input Format

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

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$, it means there is no telephone.

Output Format

One line with one integer, the minimum number of telephones that need to be added.

4 1
1 0 1 1 

1

5 2
1 0 0 0 1

1

8 2
1 1 0 0 1 0 0 1

2

Hint

Sample Explanation #1

Add a telephone on desk $2$, and then the telephone on desk $4$ can ring.

Sample Explanation #2

Add a telephone on desk $3$, and then the telephone on desk $5$ can ring.

Sample Explanation #3

Add one telephone each on desks $4$ and $7$, and then the telephone on desk $8$ can ring.

Constraints

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

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

Notes

The score of this problem follows the original COCI setting, with a full score of $80$.

Translated from COCI2016_2017 CONTEST #6 T2 TELEFONI.

Translated by ChatGPT 5