屋外开灯屋里黑

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

相传,遥远的东方有一个被遗忘许久的废弃村庄,那里无人居住,但是每当夜黑风高的时候,村落里灯火通明,仿佛喧嚣尘世一半,但无人的寂寥却平添一丝诡异……

好吧这是小亮的恶作剧,村庄里n个小屋排成一列,一些小屋的灯泡还好用,所以小亮每当夜晚会偷溜进村庄,打开几个房屋的顶灯,让村庄显得有人居住。

已知每个屋子灯泡的亮度,小亮为了利索行事,为了让村落显得更诡异,小亮会点亮一些房屋,让一些房子被照亮。

所有灯泡亮度一样为k,表示点亮房屋i后距离i小于k的屋子都会被照亮。定义第i个房屋与第j个房屋的距离为|j-i|。 

Input

 先输入两个正整数n,k(0 < k <= n <= 10^5),表示房屋中灯泡亮度。

之后一行n个正整数ai(0 <= ai <= 1),表示小亮是否需要让第i个房屋被照亮(0表示无要求,1表示需要被照亮)

Output

 每组输入输出一行,表示最少需要点亮的房屋数量。

Sample Input

6 2
0 1 1 1 1 0
5 3
1 1 1 1 1
5 2
1 0 0 0 1

Sample Output

2
1
2

Hint

第二组把房屋2点亮即可

第三组需要把点亮(0,4)or(0,3)or(1,4)or(1,3)才能保证0房屋和4房屋都被照亮。

Source

2016暑假集训结训赛 by LeiQ