屋里开灯屋外黑

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),表示每个房屋灯泡是否可用(0表示坏掉,1表示可打开)

 

Output

 每组输入输出一行,表示最少需要点亮的房屋数量,如果无法把全村照亮,输出-1.

Sample Input

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

Sample Output

2
1

Hint

 第一组把(1,4)点亮即可。1可照亮[0,2],4可照亮[3,5]。

第二组把房屋3点亮即可照亮整个村落[0,4]

Source

2016暑假集训结训赛 by LeiQ