Telephones

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.

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.

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

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