题目描述

一个办公室有 $N$ 张桌子从左至右排列，有些桌子上放了电话。

当第 $j$ 个桌子上的电话响了后，第 $i$ 个桌子上的电话也会响，当且仅当 $|j-i|\le D$。

现在给出电话的摆放情况，请你求出最小需要添加几个电话，能使最后一个桌子上的电话响起。

保证第一张桌子和最后一张桌子有电话放置。

输入格式

第一行包含两个正整数 $N$ 和 $D$，分别表示桌子个数和最大距离。

第二行包含 $N$ 个整数 $A_i$。如果 $A_i=1$，那么表示这个桌子上有电话，如果 $A_i=0$，则表示没有。

输出格式

一行，一个整数，表示最小需要添加电话个数，

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

提示

【样例解释 #1】

在 $2$ 号桌子上添加一个电话，即可使 $4$ 号桌子上的电话响起。

【样例解释 #2】

在 $3$ 号桌子上添加一个电话，即可使 $5$ 号桌子上的电话响起。

【样例解释 #3】

在 $4$ 号桌子和 $7$ 号桌子上各添加一个电话，即可使 $8$ 号桌子上的电话响起。

【数据范围】

对于 $50\%$ 的数据，$1\le N\le 20$；

对于 $100\%$ 的数据，$1\le D\le N\le 3\times 10^5$。

【说明】

本题分值按 COCI 原题设置，满分 $80$。

题目译自 COCI2016_2017 CONTEST #6 T2 TELEFONI