Telephones

Interview

Time limit1sMemory limit64 MB

Summary

Add the fewest phones to empty desks so a ring hops from the first desk to the last with each hop spanning at most D.

Level: Medium4 of 10
Topics: Greedy, Array
Solved: No attempts yet

Problem

A room holds $N$ desks in one row from left to right, each desk next to the following one. Some desks hold one telephone, and the rest are empty.

Every telephone is broken. The telephone on desk $i$ rings when the telephone on desk $j$ rings and $|j - i| \le D$ .

The first desk and the last desk always hold a telephone. At the start the leftmost telephone rings. To make the telephone on the last desk ring, you place new telephones on empty desks. Find the smallest number of new telephones.

Input

The first line contains two positive integers $N$ and $D$ ( $1 \le N \le 300000$ , $1 \le D \le N$ ).

The second line contains $N$ numbers separated by spaces, each of them $0$ or $1$ . If the $i$ -th number is $1$ , the $i$ -th desk from the left holds a telephone. If it is $0$ , that desk is empty.

Output

Print the smallest number of new telephones on the first line.

Hint

In the test cases worth $40$ points in total, $1 \le N \le 20$ holds.

Examples6

Example 1
Input
```
4 1
1 0 1 1
```
Expected output
```
1
```
Example 2
Input
```
5 2
1 0 0 0 1
```
Expected output
```
1
```
Example 3
Input
```
8 2
1 1 0 0 1 0 0 1
```
Expected output
```
2
```
Example 4
Input
```
1 1
1
```
Expected output
```
0
```
Example 5
Input
```
2 1
1 1
```
Expected output
```
0
```
Example 6
Input
```
10 1
1 0 0 0 0 0 0 0 0 1
```
Expected output
```
8
```