Vova's house is an array consisting of $n$ elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The $i$-th element of the array is $1$ if there is a heater in the position $i$, otherwise the $i$-th element of the array is $0$.

Each heater has a value $r$ ($r$ is the same for all heaters). This value means that the heater at the position $pos$ can warm up all the elements in range $[pos - r + 1; pos + r - 1]$.

Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater. 

Vova's target is to warm up the whole house (all the elements of the array), i.e. if $n = 6$, $r = 2$ and heaters are at positions $2$ and $5$, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $3$ elements will be warmed up by the first heater and the last $3$ elements will be warmed up by the second heater).

Initially, all the heaters are off.

But from the other hand, Vova didn't like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.

Your task is to find this number of heaters or say that it is impossible to warm up the whole house.


-----Input-----

The first line of the input contains two integers $n$ and $r$ ($1 \le n, r \le 1000$) — the number of elements in the array and the value of heaters.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$) — the Vova's house description.


-----Output-----

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.


-----Examples-----
Input
6 2
0 1 1 0 0 1

Output
3

Input
5 3
1 0 0 0 1

Output
2

Input
5 10
0 0 0 0 0

Output
-1

Input
10 3
0 0 1 1 0 1 0 0 0 1

Output
3



-----Note-----

In the first example the heater at the position $2$ warms up elements $[1; 3]$, the heater at the position $3$ warms up elements $[2, 4]$ and the heater at the position $6$ warms up elements $[5; 6]$ so the answer is $3$.

In the second example the heater at the position $1$ warms up elements $[1; 3]$ and the heater at the position $5$ warms up elements $[3; 5]$ so the answer is $2$.

In the third example there are no heaters so the answer is -1.

In the fourth example the heater at the position $3$ warms up elements $[1; 5]$, the heater at the position $6$ warms up elements $[4; 8]$ and the heater at the position $10$ warms up elements $[8; 10]$ so the answer is $3$.

Difficulty: MEDIUM
Tags: Amortized analysis

Greedy algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
R = lambda : map(int, input().split())
(n, r) = R()
c = p = q = 0
for (i, x) in enumerate(R()):
	if x:
		p = i + r
	if i - q > r - 2:
		if p == q:
			break
		q = p
		c += 1
print((c, c + 1, -1)[(i >= p) + (i >= q)])


(x, y) = map(int, input().split())
a = list(map(int, input().split()))
o = 0
i = 0
while i < len(a):
	r = -1
	for j in range(min(i + y - 1, len(a) - 1), max(i - y + 1, 0) - 1, -1):
		if a[j] == 1:
			o += 1
			r = j + y
			break
	if r == -1:
		print(-1)
		exit()
	i = r
print(o)


R = lambda : map(int, input().split())
(n, r) = R()
a = [*R()] + [0] * (r - 1)
p = q = -r
c = 0
for i in range(n + r - 1):
	if a[i]:
		p = i
	if i - q == 2 * r - 1:
		if p == q:
			c = -1
			break
		q = p
		c += 1
print(c)


def main():
	(n, r) = list(map(int, input().split()))
	arr = [True if c == '1' else False for c in input().split()]
	last_heated = 0
	tot = 0
	last_turned = -1
	while last_heated < n:
		optim = last_heated + r - 1
		while True:
			if optim < 0:
				print('-1')
				return
			if optim <= last_turned:
				print('-1')
				return
			if optim >= n:
				optim -= 1
				continue
			if arr[optim]:
				tot += 1
				last_heated = optim + r
				last_turned = optim
				break
			optim -= 1
	print(tot)

def __starting_point():
	main()
__starting_point()


(n, r) = map(int, input().split())
data = list(map(int, input().split()))
last = 0
ans = 0
while last < n:
	save = -1
	for i in range(max(0, last - r + 1), min(n, last + r)):
		if data[i] == 1:
			save = i
	if save == -1:
		ans = -1
		break
	else:
		ans += 1
		last = save + r
print(ans)


(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
heaters = []
counts = [0] * n
for i in range(0, n):
	if arr[i] == 0:
		continue
	heaters.append(i)
	for j in range(max(0, i - r + 1), min(n - 1, i + r - 1) + 1):
		counts[j] += 1
if 0 in counts:
	print(-1)
else:
	ret = len(heaters)
	for i in range(0, len(heaters)):
		heater_idx = heaters[i]
		found = False
		for j in range(max(0, heater_idx - r + 1), min(n - 1, heater_idx + r - 1) + 1):
			if counts[j] == 1:
				found = True
				break
		if not found:
			ret -= 1
			for j in range(max(0, heater_idx - r + 1), min(n - 1, heater_idx + r - 1) + 1):
				counts[j] -= 1
	print(ret)


from sys import stdin, stdout

def right_index_search(i, arr, k):
	j = i
	index = -1
	while j < len(arr) and j < i + k:
		if arr[j] == 1:
			index = j
		j += 1
	return index

def left_index_search(i, arr, k):
	j = i - 1
	index = -1
	while j >= 0 and j > i - k:
		if arr[j] == 1:
			index = j
			break
		j -= 1
	return index

def pylons(k, arr):
	count = 0
	i = 0
	while i < len(arr):
		index_right = right_index_search(i, arr, k)
		if index_right == -1:
			index_left = left_index_search(i, arr, k)
			if index_left == -1:
				return -1
			else:
				i = index_left + k
				count += 1
		else:
			i = index_right + k
			count += 1
	return count
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
arr = list(map(int, input().strip().split(' ')))
result = pylons(k, arr)
print(result)


import sys
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
l = 0
l1 = -1
b = [0 for i in range(n)]
for i in range(n):
	if a[i] == 0:
		continue
	ans += 1
	f = min(n, i + r)
	s = max(0, i - r + 1)
	for j in range(s, f):
		b[j] += 1
for i in range(n):
	if b[i] == 0:
		print(-1)
		sys.exit(0)
	if a[i] == 0:
		continue
	f = min(n, i + r)
	s = max(0, i - r + 1)
	ok = True
	for j in range(s, f):
		if b[j] == 1:
			ok = False
	if ok:
		for j in range(s, f):
			b[j] -= 1
		ans -= 1
print(ans)


(n, r) = map(int, input().split())
arr = [int(x) for x in input().split()]
light = [0 for x in range(n)]
heaters = 0
if max(arr) == 0 or (r == 1 and min(arr) == 0):
	print(-1)
else:
	for i in range(n):
		if arr[i] == 1:
			heaters += 1
			for j in range(max(0, i - r + 1), min(n, i + r)):
				light[j] += 1
	if not min(light):
		print(-1)
	else:
		for i in range(n):
			if arr[i] == 1:
				needed = False
				for j in range(max(0, i - r + 1), min(n, i + r)):
					light[j] -= 1
					if light[j] == 0:
						needed = True
						for k in range(max(0, i - r + 1), min(n, i + r)):
							light[k] = 9999
				if not needed:
					heaters -= 1
		print(heaters)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	prev = -1
	f = 1
	ind = 0
	ans = 0
	while ind < n:
		for i in range(ind, min(ind + r, n)):
			if a[i] == 1:
				prev = i
		if prev == -1:
			for i in range(ind, max(ind - r, 0), -1):
				if a[i] == 1:
					prev = i
					break
			if prev == -1:
				f = 0
				break
		else:
			ind = prev + r
			ans += 1
			prev = -1
	if f == 0:
		print(-1)
	else:
		print(ans)
	return
main()


(n, r) = map(int, input().split())
L = list(map(int, input().split()))
c = [0] * n
res = 0
for i in range(n):
	if L[i]:
		res += 1
		for j in range(max(0, i - r + 1), min(n, i + r)):
			c[j] += 1
for i in range(n):
	if c[i] == 0:
		print(-1)
		quit()
for i in range(n):
	f = 1
	for j in range(max(0, i - r + 1), min(n, i + r)):
		if c[j] == 1:
			f = 0
			break
	if f and L[i]:
		res -= 1
		for j in range(max(0, i - r + 1), min(n, i + r)):
			c[j] -= 1
print(res)


def solve(house, r):
	last = -1
	house[0] = -1 if house[0] == 0 else 0
	for i in range(1, len(house)):
		if house[i] == 1:
			house[i] = i
		else:
			house[i] = house[i - 1]
	count = 0
	while last < len(house) - 1:
		left = max(-1, last - r + 1)
		right = last + r
		closest = house[-1] if right >= len(house) else house[right]
		if closest > left and closest <= right:
			count += 1
			last = closest + r - 1
		else:
			return -1
	return count
(tests, r) = [int(x) for x in input().split()]
house = [int(x) for x in input().split()]
print(solve(house, r))


import sys
input = lambda : sys.stdin.readline().strip('\r\n')
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
low = 0
ans = 0
pre = -1
while low < n:
	curr = min(n - 1, low + r - 1)
	while curr > pre:
		if a[curr] == 1:
			break
		curr -= 1
	else:
		ans = -1
		break
	low = curr + r
	pre = curr
	ans += 1
print(ans)


def solve(n, r, a):
	i = k = -1
	count = 0
	while i < n:
		if i == -1:
			for j in range(min(r, n)):
				if a[j] == 1:
					i = j
		else:
			for j in range(k + 1, min(k + 2 * r, n)):
				if a[j] == 1:
					i = j
		if i == k:
			return -1
		else:
			count += 1
			k = i
			if n - k <= r:
				return count
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = solve(n, r, a)
print(ans)


def mi():
	return map(int, input().split())
(n, r) = mi()
a = list(mi())

def fun(n, a, r):
	vis = [0] * n
	i = 0
	cnt = 0
	for j in range(min(r, n)):
		if a[j] == 1:
			i = j
	while i < n:
		if vis[i] == 1 and vis[min(n, end + r) - 1] == 1:
			break
		if a[i] == 1:
			cnt += 1
			j = max(0, i - (r - 1))
			end = min(n, i + r)
			next = 0
			while j < end:
				vis[j] = 1
				j += 1
			next = 0
			for k in range(i + 1, min(n, end + r)):
				if a[k] == 1:
					next = k
			if next:
				i = next
				continue
		i += 1
	if 0 in vis:
		return -1
	else:
		return cnt
print(max(fun(n, a, r), fun(n, a[::-1], r)))


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0] * n
ans = 0
summ = 0
for i in range(n):
	if a[i] == 1:
		summ += 1
		x = max(0, int(i - m + 1))
		y = min(n - 1, int(i + m - 1))
		for j in range(x, y + 1):
			b[j] += 1
for i in range(n):
	if a[i] == 1:
		x = max(0, int(i - m + 1))
		y = min(n - 1, int(i + m - 1))
		dem = 0
		for j in range(x, y + 1):
			if b[j] >= 2:
				dem += 1
		if dem == y - x + 1:
			ans += 1
			for j in range(x, y + 1):
				b[j] -= 1
ck = True
for i in b:
	if i == 0:
		ck = False
		break
if ck:
	print(summ - ans)
else:
	print(-1)


(n, r) = map(int, input().split())
a = input().split()
i = -r
n_r = n - r
n_1 = n - 1
r1 = r * 2 - 1
res = 0
while i < n_r:
	for j in range(min(i + r1, n_1), max(i, -1), -1):
		if a[j] == '1':
			i = j
			res += 1
			break
	else:
		res = -1
		i = n_r
print(res)


(N, r) = map(int, input().split())
a = list(map(int, input().split()))
last = -1
num = 0
while last < N - 1:
	pos = -1
	for i in range(N - 1, max(-1, last - r + 1), -1):
		if a[i] == 1 and i - r <= last:
			pos = i
			break
	if pos == -1:
		print(-1)
		exit()
	num += 1
	last = pos + r - 1
print(num)


(n, r) = list(map(int, input().split(' ')))
(r, pointer, count, heaters) = (r - 1, 0, 0, list(map(int, input().split(' '))))
while pointer < n:
	offset = r
	while pointer + offset >= n or (pointer + offset >= 0 and heaters[pointer + offset] == 0 and (offset != -r - 1)):
		offset -= 1
	if pointer + offset < 0 or offset == -r - 1:
		print(-1)
		raise SystemExit(0)
	(pointer, count) = (pointer + offset + r + 1, count + 1)
print(count)


import math

def get_input_list():
	return list(map(int, input().split()))
(n, r) = get_input_list()
r = r - 1
h = get_input_list()
m = min(r, n - 1)
while h[m] == 0 and m > 0:
	m -= 1
if m == 0 and h[m] == 0:
	print(-1)
else:
	p = 0
	anws = 1
	posible = True
	while True:
		if m + r >= n - 1:
			break
		a = m + 2 * r + 1
		if a >= n:
			a = n - 1
		while h[a] == 0 and a > m:
			a = a - 1
		if a == m:
			print(-1)
			posible = False
			break
		else:
			anws += 1
			m = a
	if posible == True:
		print(anws)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
tot = 0
res = 0
lst = -1
pre = -1
for i in range(n):
	if a[i]:
		tot += 1
		if lst > pre:
			res += 1
		lst = i + r - 1
	if i >= pre + r:
		if lst > pre:
			pre = lst
		else:
			print(-1)
			exit(0)
if lst < n - 1:
	print(-1)
	exit(0)
if lst > pre and pre >= n - 1:
	res += 1
print(tot - res if tot else -1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
d = 0
while True:
	ki = min(n - 1, i + r - 1)
	while ki >= 0 and (not a[ki]):
		ki -= 1
	if ki < 0:
		d = -1
		break
	a[ki] = 0
	d += 1
	i = ki + r
	if i > n - 1:
		break
	if i < 0:
		d = -1
		break
print(d)


(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
i = min(n - 1, r - 1)
prev = -1
while i > prev:
	while i > prev and arr[i] == 0:
		i -= 1
	if i == prev:
		ans = -1
		break
	prev = i
	ans += 1
	if prev + r >= n:
		break
	i = min(n - 1, i + 2 * r - 1)
print(ans)


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
answer = 0
last_o = -r
used_o = -r
for i in range(n):
	if a[i] == 1:
		if i - used_o > 2 * (r - 1):
			last_o = i
			used_o = i
			answer += 1
		else:
			last_o = i
	elif i - used_o > 2 * (r - 1):
		if i - last_o > 2 * (r - 1):
			answer = -1
			break
		else:
			used_o = last_o
			answer += 1
if n - used_o > r:
	if n - last_o > r:
		answer = -1
	else:
		answer += 1
elif n - used_o > r:
	answer += 1
print(answer)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, r) = map(int, input().split())
house = [int(z) for z in input().split()]
cnt = 0
last = -1
lampos = 0
while lampos < n:
	endpoint = min(n - 1, lampos + r - 1)
	while house[endpoint] < 1:
		endpoint -= 1
		if endpoint < lampos + 1 - r or endpoint < 0:
			print(-1)
			exit()
	lampos = endpoint + r
	cnt += 1
print(cnt)


from itertools import accumulate
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
dom = list(map(lambda x: 0, range(n + 1)))
for (i, el) in enumerate(a):
	if el:
		dom[max(0, i - r + 1)] += 1
		dom[min(n, i + r)] -= 1
acc_d = list(accumulate(dom[:-1]))
if 0 in acc_d:
	print(-1)
	exit()
if n < r:
	print(1)
	exit()
right = -r
ans = 0
while right + r < n:
	for i in range(right, min(n, right + 2 * r))[::-1]:
		if a[i]:
			right = i
			ans += 1
			break
print(ans)


(n, r) = map(int, input().split())
b = list(map(int, input().split()))
arr = [0 for _ in range(n)]
for i in range(n):
	if b[i] == 1:
		for j in range(i - r + 1, i + r):
			if j > -1 and j < n:
				arr[j] = max(b[j], i + 1)
flag = 0
c = 0
i = 0
while i < n:
	if arr[i] == 0:
		flag = 1
		break
	else:
		c = c + 1
		i = arr[i] + r - 1
if flag == 1:
	print(-1)
else:
	print(c)


import sys

def minp():
	return sys.stdin.readline().strip()
(n, r) = map(int, minp().split())
k = r
f = None
fl = None
res = 0
i = 0
for a in map(int, minp().split()):
	if i == k:
		if f == None:
			print(-1)
			exit(0)
		fl = f
		k = f + 2 * r
		f = None
		res += 1
	if a == 1:
		f = i
	i += 1
if fl == None or i - fl > r:
	if f == None:
		print(-1)
		exit(0)
	if i - f > r:
		print(-1)
		exit(0)
	res += 1
print(res)


import sys
(n, r) = map(int, input().split())
A = list(map(int, input().split()))
count = 0
i = 0
while i < n:
	for j in range(min(i + r - 1, n - 1), max(i - r, -1), -1):
		if A[j] == 1:
			count += 1
			if j + r > i:
				i = j + r
				break
			else:
				print(-1)
				sys.exit()
	else:
		print(-1)
		sys.exit()
print(count)


def min(a, b):
	if a < b:
		return a
	else:
		return b

def serc(x, d):
	if d < 0:
		return 1000000000
	if x == n:
		if d < r - 1:
			return 1000000000
		return 0
	if dp[x][d] != -1:
		return dp[x][d]
	dp[x][d] = 1000000000
	if ar[x] == 1:
		dp[x][d] = min(dp[x][d], 1 + serc(x + 1, (r - 1) * 2))
	dp[x][d] = min(dp[x][d], serc(x + 1, d - 1))
	return dp[x][d]
dp = []
ar = []
for i in range(1005):
	dp.append([])
	for j in range(2005):
		dp[i].append(-1)
	ar.append(0)
read = input().split(' ')
n = int(read[0])
r = min(n, int(read[1]))
read = input().split(' ')
for i in range(n):
	ar[i] = int(read[i])
ans = serc(0, r - 1)
if ans == 1000000000:
	ans = -1
print(ans)


(n, r) = map(int, input().split())
arr = [1] + [0] * (r - 1) + [int(i) for i in input().split()]
n = len(arr)
(i, prev, ans, crutch) = (0, 0, 0, False)
while i < n - 1:
	ans += 1
	prev = i
	i += 2 * r - 1
	if prev + r - 1 >= n - 1:
		if crutch:
			print(ans - 1)
			break
		print(-1)
		break
	if i > n - 1:
		i = n - 1
	while i > prev:
		if arr[i] == 1:
			crutch = True
			break
		i -= 1
	else:
		print(-1)
		break
else:
	print(ans)


(n, r) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
(poss, lamp, left, right) = (True, 0, -1, min(r - 1, n - 1))
while right > left:
	while right > left and a[right] != 1:
		right -= 1
	if left == right:
		poss = False
		break
	else:
		lamp += 1
		left = right
		if left + (r - 1) >= n - 1:
			break
		right = min(n - 1, left + 2 * r - 1)
if poss:
	print(lamp)
else:
	print(-1)


(n, r) = map(int, input().split())
str = '0' + ''.join(input().split())
flag = 1
heaters = 0
last = 0
while last < n:
	pos = -1
	a = max(1, last - r + 2)
	test_str = str[a:last + r + 1]
	for i in range(len(test_str)):
		if test_str[i] == '1':
			pos = i
	if pos == -1:
		flag = 0
		break
	last = a + pos + r - 1
	heaters += 1
if flag:
	print(heaters)
else:
	print(-1)


(n, r) = map(int, input().split())
h = list(map(int, input().split()))
h2 = [0] * len(h)
f = False
aux = 0
i = 0
while i < len(h2):
	f = False
	for j in range(r - 1, -r, -1):
		if h[max(0, min(i + j, n - 1))] == 1:
			i = i + j + r
			aux += 1
			f = True
			break
	if f == False:
		aux = -1
		break
print(aux)


(n, r) = map(int, input().split())
a = input().split()

def solve():
	ret = 0
	i = 0
	while i < n:
		for j in range(min(i + r - 1, n - 1), max(-1, i - r), -1):
			if a[j] == '1':
				ret += 1
				i = j + r
				break
		else:
			return -1
	return ret
print(solve())


import sys
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, r) = inpl()
a = inpl()
b = [False] * n
res = 0
for i in range(n):
	if b[i]:
		continue
	for j in range(-r + 1, r)[::-1]:
		if i + j >= n or i + j < 0:
			continue
		if a[i + j]:
			for k in range(i + j - r + 1, i + j + r):
				if 0 <= k < n:
					b[k] = True
			res += 1
			break
if sum(b) == n:
	print(res)
else:
	print(-1)


(n, k) = map(int, input().split())
lis = list(map(int, input().split()))
ans = [0] * (n + 2)
cou = 0
for i in range(n):
	if lis[i] == 1:
		cou += 1
		l = max(0, i - k + 1)
		r = min(n - 1, i + k - 1)
		for j in range(l, r + 1):
			ans[j] += 1
if min(ans[:n]) == 0:
	print('-1')
	exit()
fin = 0
for i in range(n):
	if lis[i] == 1:
		l = max(0, i - k + 1)
		r = min(n - 1, i + k - 1)
		c = 1
		for j in range(l, r + 1):
			if ans[j] == 1:
				c = 0
		if c:
			fin += 1
			for j in range(l, r + 1):
				ans[j] -= 1
print(cou - fin)


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
res = 0
last_heater_pos = -r
while n - last_heater_pos > r or last_heater_pos < 0:
	next_heaters_pos = [i for i in range(max(0, last_heater_pos + 1), min(last_heater_pos + 2 * r, n)) if a[i] == 1]
	if next_heaters_pos:
		last_heater_pos = max(next_heaters_pos)
		res += 1
	else:
		print(-1)
		exit()
print(res)


def solve(arr):
	if 1 in arr[::-1]:
		return len(arr) - arr[::-1].index(1) - 1
	return -1
(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
flag = 1
curr = r
t = -1
count = 0
while True:
	tt = t
	t = solve(arr[t + 1:curr]) + t + 1
	if t == tt:
		flag = 0
		break
	curr = 2 * r + t
	count += 1
	if curr > n:
		curr = n
	if t + r >= n:
		break
	if t + 1 >= n:
		break
if flag == 1:
	print(count)
else:
	print(-1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
(n, k) = map(int, input().split())
ls = list(map(int, input().split()))
total = 0
curr = 0
while curr < n:
	f = 0
	for i in range(min(curr + k - 1, n - 1), max(-1, curr - k), -1):
		if ls[i] == 1:
			curr = i + k
			f = 1
			total += 1
			break
	if f == 0:
		print(-1)
		exit()
print(total)


import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, r) = MAP()
A = [0] + LIST()
B = []
for (i, a) in enumerate(A):
	if a:
		B.append(i)
M = len(B)
dp = list2d(M + 1, M + 1, -INF)
dp[0][0] = 0
for (i, b) in enumerate(B):
	for j in range(M + 1):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if dp[i][j] >= b - r:
			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], b + r - 1)
ans = INF
for j in range(M + 1):
	if dp[M][j] >= N:
		ans = j
		break
if ans == INF:
	print(-1)
else:
	print(ans)


(n, r) = map(int, input().split())
list_a = list(map(int, input().split()))
count = 0
next = 0
i = 0
ans = 0
if n <= r:
	if 1 in list_a:
		count = 1
	else:
		ans = -1
else:
	while True:
		if i > r - 1:
			ans = -1
			break
		elif list_a[r - 1 - i] == 1:
			next = r - 1 - i
			count += 1
			break
		else:
			i += 1
	flag = 0
	if ans != -1:
		while True:
			i = 0
			while True:
				if i >= 2 * (r - 1) + 1:
					ans = -1
					break
				try:
					if list_a[next + 2 * (r - 1) + 1 - i] == 1:
						next += 2 * (r - 1) + 1 - i
						count += 1
						break
					else:
						i += 1
				except IndexError:
					flag = 1
					break
			if ans == -1 or flag == 1:
				break
	if ans != -1:
		if next >= n - r:
			pass
		else:
			while True:
				if i > r - 1:
					ans = -1
					break
				elif list_a[-r + i] == 1:
					count += 1
					break
				else:
					i += 1
if ans == -1:
	print(ans)
else:
	print(count)


(n, r) = map(int, input().split())
(a, ans, p1) = (list(map(int, input().split())), 0, 0)
while p1 < n:
	flag = 0
	for i in range(min(n - 1, p1 + r - 1), p1 - 1, -1):
		if a[i]:
			ans += 1
			p1 = i + r
			flag = 1
			a[i] = 0
			break
	if flag == 0:
		c = 1
		for i in range(p1 - 1, max(-1, p1 - r), -1):
			if a[i]:
				ans += 1
				p1 = i + r
				flag = 1
				a[i] = 0
				break
			c += 1
	if flag == 0:
		ans = -1
		break
print(ans)


(n, r) = map(int, input().split())
a = [int(i) for i in input().split()]
prevT = -1
result = 0
prevH = 0
flag = 0
while prevH < n:
	if flag == 0:
		aux = prevH + (r - 1)
		while 1:
			if aux < 0 or prevT >= aux:
				print(-1)
				flag = 1
				break
			if aux >= n:
				aux = aux - 1
				continue
			if a[aux] == 1:
				prevH = aux + r
				prevT = aux
				result = result + 1
				break
			aux = aux - 1
	else:
		break
if flag != 1:
	print(result)


(n, r) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
enabled = [0] * n
ans = 0
i = 0
breaked = False
while i < n:
	j = i + r - 1
	heater = -1
	while j >= i - r + 1:
		if j >= 0 and j < n and (a[j] == 1):
			heater = j
			break
		j -= 1
	if heater == -1:
		breaked = True
		break
	else:
		i = heater + r
	ans += 1
if not breaked:
	print(ans)
else:
	print(-1)


def main():
	(n, r) = map(int, input().split())
	a = [int(e) for e in input().split()]
	r -= 1
	fr = 0
	ans = 0
	while fr < n:
		i = min(fr + r, n - 1)
		flag = False
		while i >= max(fr - r, 0) and (not flag):
			if a[i] == 1:
				ans += 1
				fr = i + r + 1
				flag = True
				break
			i -= 1
		if not flag:
			print(-1)
			return
	print(ans)
main()


nos = list(map(int, input().split()))
arr = list(map(int, input().split()))
(i, j, minj) = (0, len(arr) - 1, len(arr))
(heater, lock) = (0, 0)
while i < len(arr) and j >= 0:
	if arr[j]:
		if lock == 0 and minj == j:
			heater = -1
			break
		if abs(i - j) <= nos[1] - 1:
			if lock == 0:
				if minj != j:
					minj = j
				heater += 1
			lock = 1
			i += 1
			continue
		elif i < j:
			j -= 1
		else:
			lock = 0
			j = len(arr) - 1
	else:
		j -= 1
if len(arr) > 0 and heater == 0:
	print(-1)
else:
	print(heater)


(n, r) = [int(el) for el in input().split()]
a = [int(el) for el in input().split()]
if n == 1 and a[0] == 0:
	print(-1)
	raise SystemExit
if n == 1 and a[0] == 1:
	print(1)
	raise SystemExit
out = 0
i = r - 1
mx = 0
j = -1
while mx < n - 1:
	q = 0
	if i > n - 1:
		start = n - 1
	else:
		start = i
	end = j
	for j in range(start, end, -1):
		if a[j] == 1:
			i = j + 2 * r - 1
			q = 1
			mx = j + r - 1
			out += 1
			break
	if q == 0:
		print(-1)
		raise SystemExit
print(out)


import sys

class Input(object):

	def __init__(self):
		self.fh = sys.stdin

	def next_line(self):
		return sys.stdin.readline()

	def next_line_ints(self):
		line = self.next_line()
		return [int(x) for x in line.split()]

def get_min_heaters(n, r, valid_array):
	count = 0
	unheat_pos = 0
	while unheat_pos < len(valid_array):
		heater_pos = min(len(valid_array) - 1, unheat_pos + r - 1)
		min_accept_pos = max(0, unheat_pos - r + 1)
		while heater_pos >= min_accept_pos and valid_array[heater_pos] == 0:
			heater_pos -= 1
		if heater_pos < min_accept_pos:
			return -1
		count += 1
		unheat_pos = heater_pos + r
	return count

def main():
	input = Input()
	while True:
		nums = input.next_line_ints()
		if not nums:
			break
		(n, r) = nums
		valid_array = input.next_line_ints()
		heaters = get_min_heaters(n, r, valid_array)
		print('{}'.format(heaters))
main()


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
x = [0] * n
for i in range(n):
	if a[i] == 1:
		for j in range(i - r + 1, i + r):
			if j > -1 and j < n:
				x[j] = max(a[j], i + 1)
ans = 0
i = 0
while i < n:
	if x[i] == 0:
		ans = -1
		break
	else:
		ans += 1
		i = x[i] + r - 1
print(ans)


inf = float('inf')
(n, r) = map(int, input().split())
l = list(map(int, input().split()))
dp = [inf] * n
for i in range(r):
	if i < n and l[i]:
		dp[i] = 1
for i in range(n):
	if l[i]:
		for j in range(i - (r - 1) - (r - 1) - 1, i):
			if j < 0:
				continue
			if dp[j] != inf:
				dp[i] = min(dp[i], dp[j] + 1)
res = inf
for i in range(n - (r - 1) - 1, n):
	if i < 0:
		continue
	res = min(res, dp[i])
if res == inf:
	print(-1)
else:
	print(res)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
unheated = 0
while unheated < len(a):
	choose = -1
	for i in range(min(len(a) - 1, unheated + r - 1), max(0, unheated - r + 1) - 1, -1):
		if a[i] == 1:
			ans += 1
			choose = i
			break
	if choose == -1:
		print(-1)
		exit(0)
	unheated = choose + r
print(ans)


def main():
	(n, r) = map(int, input().split())
	arr = list(map(int, input().split()))
	times = [0] * len(arr)
	for i in range(len(arr)):
		if arr[i] == 1:
			for j in range(max(i - r + 1, 0), min(i + r, len(arr))):
				times[j] += 1
	for v in times:
		if v == 0:
			print(-1)
			exit(0)
	cnt = 0
	for i in range(len(times)):
		if arr[i] == 1:
			toRemove = True
			for j in range(max(i - r + 1, 0), min(i + r, len(arr))):
				if times[j] == 1:
					toRemove = False
					break
			if toRemove:
				cnt += 1
				for j in range(max(i - r + 1, 0), min(i + r, len(arr))):
					times[j] -= 1
	print(arr.count(1) - cnt)
main()


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
lo = 0
ans = 0
pre = -1
while lo < n:
	to = min(n - 1, lo + r - 1)
	while to > pre:
		if a[to] == 1:
			break
		to -= 1
	else:
		ans = -1
		break
	lo = to + r
	pre = to
	ans += 1
print(ans)


def solve(n, r, a):
	ans = 0
	last = -1
	while last < n - 1:
		pos = -1
		for i in range(n - 1, max(-1, last - r + 1), -1):
			if a[i] == 1 and i - r <= last:
				pos = i
				break
		if pos == -1:
			return -1
		ans += 1
		last = pos + r - 1
	return ans
ans = []
(n, r) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
print(solve(n, r, a))


(a, b) = [int(z) for z in input().split()]
y = input().split()
h = b
q = 0
t = True
f = -1
Z = True
r = 0
for i in range(a):
	if i < h:
		if y[i] == '1':
			if t:
				q += 1
				t = False
			f = i
	else:
		if f == -1:
			Z = False
			break
		h = f + 2 * b
		t = True
		f = -1
		if y[i] == '1':
			if t:
				q += 1
				t = False
			f = i
	if y[i] == '1':
		r = 0
	else:
		r += 1
	if f + b >= len(y) and f != -1:
		break
if Z and q != 0 and (f != -1) and (r < b):
	print(q)
else:
	print(-1)


(n, r) = list(map(int, input().split()))
mas = list(map(int, input().split()))
masn = [0 for i in range(n)]
for i in range(n):
	if mas[i] == 1:
		for j in range(max(0, i - r + 1), min(n, i + r)):
			masn[j] = i + 1
ind = 0
otv = 0
br = False
while ind < n:
	if masn[ind] > 0:
		otv += 1
		ind = masn[ind] - 1 + r
	else:
		br = True
		break
if br:
	print(-1)
else:
	print(otv)


(n, r) = map(int, input().split())
room = list(map(int, input().split()))
last = -1
ans = 0
trig = True
while trig:
	if last + r < n:
		for i in range(last + r, max(-1, last - r + 1), -1):
			if room[i] == 1:
				last = i + r - 1
				ans += 1
				break
			elif i == max(-1, last - r + 1) + 1:
				ans = -1
				trig = False
			else:
				pass
	elif last >= n - 1:
		trig = False
	else:
		for i in range(n - 1, max(-1, last - r + 1), -1):
			if room[i] == 1:
				last = i + r - 1
				ans += 1
				if last >= n - 1:
					trig = False
				break
			elif i == max(-1, last - r + 1) + 1:
				ans = -1
				trig = False
			else:
				pass
print(ans)


def add(cnt, l, r, delta):
	for i in range(l, r):
		cnt[i] += delta
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0 for i in range(n)]
sooca = 0
for i in range(n):
	if a[i] == 1:
		add(cnt, max(0, i - r + 1), min(n, i + r), 1)
for i in cnt:
	if i == 0:
		print(-1)
		exit(0)
ans = a.count(1)
for i in range(n):
	if a[i] == 0:
		continue
	if not any((x == 1 for x in cnt[max(0, i - r + 1):min(n, i + r)])):
		add(cnt, max(0, i - r + 1), min(n, i + r), -1)
		ans -= 1
print(ans)


(n, r) = map(int, input().split())
location = list(map(int, input().split()))
heaterlist = []
for i in range(len(location)):
	if location[i] == 1:
		heaterlist.append(i)
heaterlist.append(10000000)
don = 0
if heaterlist[0] >= r or heaterlist[-2] < n - r:
	print(-1)
	don = 1
for i in range(len(heaterlist) - 2):
	if heaterlist[i + 1] - heaterlist[i] > 2 * r - 1 and don == 0:
		print(-1)
		don = 1
unheated = 0
usedheaters = []
if don == 0:
	while unheated < n:
		i = 0
		while heaterlist[i] < unheated + r:
			good = heaterlist[i]
			i += 1
		usedheaters.append(good)
		unheated = usedheaters[-1] + r
	print(len(usedheaters))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)

def solve(case):
	(n, r) = sep()
	a = lis()
	pre = [0] * (n + 1)
	for i in range(n):
		if a[i] == 1:
			pre[max(0, i - r + 1)] += 1
			pre[min(n, i + r)] -= 1
	for i in range(1, n + 1):
		pre[i] += pre[i - 1]
	for i in range(n):
		if pre[i] == 0:
			print(-1)
			return
	ans = 0
	for i in range(n):
		l = max(0, i - r + 1)
		rr = min(n, i + r)
		f = True
		for j in range(l, rr):
			if pre[j] == 1:
				f = False
		if f:
			ans += 1
			for j in range(l, rr):
				pre[j] -= 1
	print(sum(a) - ans)
testcase(1)


(n, r) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
idx = 0
cb = -100000
ptr = 0
count = 0
flag = True
while idx < n:
	ptr = max(0, idx - r + 1)
	while ptr < min(n, idx + r):
		if a[ptr] == 1:
			cb = ptr
		ptr += 1
	if abs(idx - cb) >= r:
		print(-1)
		flag = False
		break
	else:
		count += 1
		idx = cb + r
if flag:
	print(count)


def add(cnt, l, r, delta):
	for i in range(l, r):
		cnt[i] += delta

def can_delete(cnt, l, r):
	for i in range(l, r):
		if cnt[i] < 2:
			return False
	return True
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0 for i in range(n)]
sooca = 0
for i in range(n):
	if a[i] == 1:
		add(cnt, max(0, i - r + 1), min(n, i + r), 1)
for i in cnt:
	if i == 0:
		print(-1)
		exit(0)
ans = a.count(1)
for i in range(n):
	if a[i] == 0:
		continue
	if can_delete(cnt, max(0, i - r + 1), min(n, i + r)):
		add(cnt, max(0, i - r + 1), min(n, i + r), -1)
		ans -= 1
print(ans)


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	(n, r) = get_ints()
	arr = get_list()
	start = 0
	poss = True
	ans = 0
	while start < n:
		heater = -1
		left = max(0, start - r + 1)
		right = min(n, start + r)
		for i in range(left, right):
			if arr[i] == 1:
				heater = i
		if heater == -1:
			poss = False
			break
		start = heater + r
		ans += 1
	if poss == True:
		print(ans)
	else:
		print(-1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
(sum, ans, p2, p1) = (0, 0, -1, -1)
for i in range(n):
	if a[i] == 1:
		sum += 1
		if p2 > p1:
			ans += 1
		p2 = i + r - 1
	if i >= p1 + r:
		if p2 > p1:
			p1 = p2
		else:
			print(-1)
			exit()
if p2 < n - 1:
	print(-1)
	exit()
if p2 > p1 and p1 >= n - 1:
	ans += 1
print(sum - ans if sum else -1)


R = lambda : map(int, input().split())
(z, r) = R()
p = q = -1
a = 0
for (i, x) in enumerate(R()):
	if x:
		p = i + r - 1
	if i - q == r:
		if p == q:
			break
		q = p
		a += 1
print((a, a + 1, -1)[(i > p) + (i > q)])


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
if 1 not in a:
	print(-1)
else:
	s = [False] * n
	current = [False] * n
	for i in range(n):
		if a[i] == 1:
			q1 = max(0, i - r + 1)
			q2 = min(i + r, n)
			for j in range(q1, q2):
				current[j] = True
	if False in current:
		print(-1)
	elif n <= r:
		print(1)
	else:
		step = r - 1
		amount = 0
		ans = 0
		while False in s:
			while a[step] != 1:
				step -= 1
			if step < r:
				q = min(step + r, n)
				for j in range(q):
					s[j] = True
			else:
				q1 = step - r + 1
				q2 = min(step + r, n)
				for j in range(q1, q2):
					s[j] = True
			step += 2 * r - 1
			if step >= n:
				step = n - 1
			ans += 1
		print(ans)


(n, r) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
i = ans = 0
while i < n:
	pointer = i
	f = 0
	while pointer < n:
		if pointer - r + 1 > i:
			break
		if a[pointer] == 1:
			j = pointer
			f = 1
		pointer += 1
	if f == 0:
		pointer = i - 1
		while pointer >= 0:
			if pointer + r - 1 < i:
				break
			if a[pointer] == 1:
				j = pointer
				f = 1
				break
			pointer -= 1
	if f == 0:
		break
	ans += 1
	i = j + r
if f == 0:
	print(-1)
else:
	print(ans)


(n, r) = map(int, input().split())
l = list(map(int, input().split()))
c = [0] * n
ans = 0
for i in range(n):
	if l[i] == 1:
		b = False
		for j in range(i - (r - 1), i + r):
			if j < 0 or j >= n:
				continue
			if c[j] != 1:
				b = True
			c[j] = 1
		if b:
			ans += 1
if c.count(0) == 0:
	ans = 1
	i = 0
	for j in range(r - 1, -1, -1):
		if j >= n:
			continue
		if l[j] == 1:
			i = j
			break
	while True:
		if i + r - 1 >= n - 1:
			break
		for j in range(i + 2 * (r - 1) + 1, i, -1):
			if j >= n:
				continue
			if l[j] == 1:
				ans += 1
				i = j
				break
		if i + r - 1 >= n - 1 or i == n - 1:
			break
	print(ans)
else:
	print(-1)


(n, r) = map(int, input().split())
h = list(map(int, input().split()))
ans = 0
p = -1
for i in range(len(h)):
	if h[i] == 1:
		if i - r > p:
			ans = 0
			break
		temp = 0
		for j in range(i, len(h)):
			if h[j] == 1:
				if j - r <= p:
					temp = j + r - 1
				else:
					break
		ans += 1
		p = temp
		if p >= n - 1:
			break
if ans and p >= n - 1:
	print(ans)
else:
	print(-1)


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
r -= 1

def f():
	prev = [0] * n
	last = -1
	for i in range(n):
		if a[i]:
			last = i
		prev[i] = last
	nb = 0
	i = 0
	while i < n:
		j = prev[min(i + r, n - 1)]
		if j < 0 or j + r < i:
			return -1
		nb += 1
		i = j + r + 1
	return nb
print(f())


(n, r) = map(int, input().split())
a = list(map(int, input().split()))

def oleft(i):
	for j in range(min(i + r - 1, n - 1), max(-1, i - r), -1):
		if a[j]:
			return j + r
	return 10 ** 6

def oright(i):
	for j in range(max(0, i - r + 1), min(i + r, n)):
		if a[j]:
			return j - r
	return -10 ** 6
(mi, ma) = (0, n - 1)
s = 0
while mi <= ma:
	mi = oleft(mi)
	s += mi - r != ma + r
	if mi > ma or mi == 10 ** 6:
		break
	ma = oright(ma)
	if ma == -10 ** 6:
		mi = -ma
		break
	s += mi - r != ma + r
if mi == 10 ** 6:
	print(-1)
else:
	print(s)


(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
covered = [set() for _ in range(n)]
for i in range(n):
	if arr[i] == 1:
		for j in range(max(0, i - r + 1), min(n, i + r)):
			covered[j].add(i)
visited = set()
for i in range(n):
	if covered[i] == set():
		print(-1)
		break
	if visited.intersection(covered[i]) == set():
		visited.add(max(covered[i]))
else:
	print(len(visited))


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 0
poscnt = 0
locs = list()
for i in range(n):
	if a[i] == 1:
		poscnt += 1
		locs.append(i)
if poscnt == 0:
	print(-1)
else:
	loc = -1
	left = right = 0
	while right < n:
		left = right
		flag = False
		while 1:
			if loc + 1 < poscnt and locs[loc + 1] < left + r:
				flag = True
				loc += 1
			else:
				break
		if flag == False:
			ans = -1
			break
		else:
			right = locs[loc] + r
			if right - 1 < left:
				ans = -1
				break
			ans += 1
	print(ans)


(n, r) = map(int, input().split())
a = tuple(map(int, input().split()))
i = 0
c = 0
while i < n:
	j = min(n - 1, i + r - 1)
	while not a[j]:
		j -= 1
		if j < 0 or j < i - r + 1:
			print(-1)
			exit()
	c += 1
	i = j + r
print(c)


def ans(n, r, a):
	a.insert(0, 0)
	(p, l, pl, cnt) = (0, 0, 0, 0)
	for i in range(1, n + 1):
		if i == p + r:
			if a[i] == 1:
				cnt += 1
				pl = i
				p = i + r - 1
			elif l > pl:
				cnt += 1
				pl = i
				p = l + r - 1
			else:
				return -1
		if a[i] == 1:
			l = i
	if l == 0:
		return -1
	if n > p:
		if l > n - r:
			cnt += 1
		else:
			return -1
	return cnt
(n, r) = map(int, input().split())
a = [int(i) for i in input().split()]
print(ans(n, r, a))


(n, r) = map(int, input().split())
a = [int(i) for i in input().split()]
j = 1
cur = 1
ans = 0
best_cur = 0
while cur <= n + 1 and j <= n:
	if cur - r + 1 <= j and cur <= n:
		if a[cur - 1] == 1:
			best_cur = cur
	elif best_cur != 0:
		j = best_cur + r
		ans += 1
		best_cur = 0
		cur -= 1
	else:
		ans = -1
		break
	cur += 1
print(ans)


ab = list(map(int, input().split()))
a = ab[0]
b = ab[1]
c = list(map(int, input().split()))
s = [0] * a
idx = 0
while True:
	tmp = -1
	for j in range(idx - b + 1, idx + b):
		if j >= 0 and j < a and (c[j] == 1):
			tmp = j
	if tmp == -1:
		print(-1)
		exit()
	s[tmp] = 1
	idx = tmp + b
	if idx >= a:
		break
print(sum(s))


def compute(n, r, array):
	num_heaters = sum(array)
	if num_heaters == 0:
		return -1
	heater_pos = set()
	array_zeroed = [0] * n
	for (i, e) in enumerate(array):
		if e == 1:
			heater_pos.add(i)
			for j in range(max(0, i - r + 1), min(i + r, n)):
				array_zeroed[j] += 1
	for elm in array_zeroed:
		if elm == 0:
			return -1
	heaters_on = 0
	house = array_zeroed.copy()
	for h in heater_pos:
		for j in range(h - r + 1, h + r):
			if 0 <= j < n:
				house[j] -= 1
		for e in house:
			if e == 0:
				heaters_on += 1
				for j in range(h - r + 1, h + r):
					if 0 <= j < n:
						house[j] += 1
				break
	return heaters_on

def main():
	(n, r) = [int(c) for c in input().split()]
	array = [int(c) for c in input().split()]
	res = compute(n, r, array)
	print(res)
main()


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
cnt = 0
for i in range(n):
	if a[i] == 1:
		cnt += 1
		le = max(0, i - r + 1)
		ri = min(n, i + r)
		for j in range(le, ri):
			b[j] += 1
for i in b:
	if i == 0:
		print(-1)
		quit()
for i in range(n):
	if a[i] == 1:
		fl = True
		le = max(0, i - r + 1)
		ri = min(n, i + r)
		for j in range(le, ri):
			if b[j] == 1:
				fl = False
				break
		if fl == True:
			cnt -= 1
			for j in range(le, ri):
				b[j] -= 1
print(cnt)


(n, r) = map(int, input().split(' '))
array = list(map(int, input().split(' ')))
i = 0
sol = True
heaters = 0
while i < n:
	found = False
	maxLimit = min(n - 1, i + r - 1)
	minLimit = max(i - r + 1, 0)
	while maxLimit >= minLimit:
		if array[maxLimit]:
			found = True
			break
		maxLimit -= 1
	if found:
		heaters += 1
		i = min(n, maxLimit + r)
	else:
		sol = False
		break
if sol:
	print(heaters)
else:
	print(-1)


(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
ptr = 0
total = 0
while ptr < n:
	good = False
	for i in range(min(ptr + r - 1, n - 1), max(ptr - r, -1), -1):
		if arr[i] == 1:
			good = True
			ptr = i + r
			total += 1
			break
	if not good:
		total = -1
		break
print(total)


from sys import stdin
input = stdin.readline
(n, r) = map(int, input().split())
arr = [int(x) for x in input().split()]
dp = [0] * n
for i in range(n):
	if arr[i] == 1:
		s = min(i + r - 1, n - 1)
		e = max(i - r + 1, 0)
		while s >= e and dp[s] == 0:
			dp[s] = 1
			s = s - 1
if dp.count(0) > 0:
	print(-1)
	exit()
dp = []
for i in range(n):
	if arr[i] == 1:
		rr = min(i + r - 1, n - 1)
		ll = max(0, i - r + 1)
		dp.append((ll, rr))
l = len(dp)
ans = []
i = 0
while i < l:
	if dp[i][0] > 0:
		break
	i = i + 1
ans.append(dp[i - 1])
s = i
for i in range(s, l):
	if i == l - 1:
		if ans[-1][1] < n - 1:
			ans.append(dp[i])
	elif dp[i + 1][0] - ans[-1][1] >= 2:
		ans.append(dp[i])
print(len(ans))


(n, r) = map(int, input().split())
lst = [*map(int, input().split())]
(item, last, prev, res, i) = (r, -1, -1, 0, 0)
for (i, x) in enumerate(lst[:r]):
	if x == 1:
		last = i
from sys import exit
if last == prev:
	print(-1)
	exit()
(prev, i, res, item) = (last, last + 1, 1, r * 2 - 1)
while i < n:
	if item == 0:
		if last == prev:
			print(-1)
			exit()
		(prev, i) = (last, last + 1)
		item = r * 2 - 1
		res += 1
	if lst[i] == 1:
		last = i
	i += 1
	item -= 1
if n - prev - 1 >= r:
	if last == prev:
		print(-1)
		exit()
	if n - last - 1 >= r:
		print(-1)
		exit()
	res += 1
print(res)


(n, r) = map(int, input().split(' '))
heaters = list(map(int, input().split(' ')))
heated = [0] * len(heaters)
heaters_cnt = 0
i = 0
while i < len(heated):
	flag = False
	for j in range(r - 1, -r, -1):
		if heaters[max(0, min(i + j, n - 1))] == 1:
			heaters_cnt += 1
			flag = True
			i = i + j + r
			break
	if not flag:
		heaters_cnt = -1
		break
print(heaters_cnt)


from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf(sp=' '):
	return [int(i) for i in get().split(sp)]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join([str(i) for i in a]) + end)

def main():
	(n, r) = getf()
	a = getf()
	b = []
	for i in range(n):
		if a[i] == 1:
			b.append([i - r + 1, i + r - 1])
	b.sort()
	lst = 0
	ans = 0
	x = n * n
	i = 0
	b += [[n + n, n]]
	k = len(b)
	while i < k:
		if lst >= n:
			break
		if b[i][0] <= lst:
			x = i
			i += 1
		else:
			if x >= k:
				pass
			elif b[x][0] <= lst:
				lst = b[x][1] + 1
				ans += 1
			else:
				i += 1
			x = -1
	if lst >= n:
		put(ans)
	else:
		put(-1)
main()


(n, r) = map(int, input().split())
a = [0] + list(map(int, input().split()))
l = 0
i = 1
end = 0
while i <= n:
	j = i + r - 1
	j = min(j, n)
	while j >= end and j <= n and (a[j] < 1):
		j -= 1
	if j > end:
		l += 1
		end = j
		i = j + r
	else:
		l = -1
		break
print(l)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
mb = True
fin = [0 for i in range(n)]
ans = 0
for i in range(n):
	if fin[i] == 0:
		for pos in range(min(i + r - 1, n - 1), max(i - r + 1, 0) - 1, -1):
			if a[pos] == 1:
				ans += 1
				for c in range(max(pos - r + 1, 0), min(pos + r - 1, n - 1) + 1):
					fin[c] = 1
				i = min(i + r - 1, n - 1) + 1
				break
for i in fin:
	if i == 0:
		print(-1)
		exit()
print(ans)


(n, r) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
b = []
j = 0
for i in range(n):
	if a[i] == 1:
		b.append(i)
i = 0
m = len(b)
ans = 0
while i < n:
	while j + 1 < m and b[j + 1] <= i + r - 1:
		j = j + 1
	if j < m and b[j] <= i + r - 1 and (b[j] >= i - r + 1):
		ans = ans + 1
	else:
		ans = -1
		break
	i = b[j] + r
print(ans)


def obogrevately(r, lst):
	(result, end) = (0, -1)
	while end < len(lst) - 1:
		position = -1
		for i in range(len(lst) - 1, max(-1, end - r + 1), -1):
			if lst[i] == 1 and i - r <= end:
				position = i
				break
		if position == -1:
			return -1
		result += 1
		end = position + r - 1
	return result
(N, R) = [int(j) for j in input().split()]
a = [int(x) for x in input().split()]
print(obogrevately(R, a))


import math
(n, r) = map(int, input().split())
a = r
z = list(map(int, input().split()))
ans = []
for i in range(len(z)):
	if z[i] == 1:
		ans.append(i)
from bisect import bisect_left
if len(ans) == 0:
	print(-1)
	exit()
start = math.inf
for i in range(len(ans)):
	if ans[i] <= a - 1:
		start = i
if start == math.inf:
	print(-1)
	exit()
else:
	mini = math.inf
	flag = 1
	for i in range(0, start + 1):
		count = 1
		tempa = ans[i]
		while 1:
			if tempa + r >= len(z):
				flag = 0
				mini = min(mini, count)
				break
			ram = bisect_left(ans, tempa + 2 * r - 1)
			if ram < len(ans):
				if ans[ram] <= tempa + 2 * r - 1 and ans[ram] != tempa:
					count += 1
				elif ans[ram] > tempa + 2 * r - 1:
					ram -= 1
					if ans[ram] == tempa:
						flag = 1
						break
					else:
						count += 1
				tempa = ans[ram]
			elif ans[-1] - tempa <= 2 * r - 1:
				if ans[-1] + r >= len(z):
					flag = 0
					mini = min(mini, count + 1)
					break
				else:
					break
			else:
				break
	if flag == 0:
		print(mini)
	else:
		print(-1)


(n, r) = map(int, input().split())
l = list(map(int, input().split()))
ka = [0] * n
flag = 0
for i in range(n):
	if l[i] == 1:
		z1 = i - r + 2
		z2 = i + r
		z1 = max(1, z1)
		z2 = min(n, z2)
		for i in range(z1 - 1, z2):
			ka[i] += 1
count = 0
for _ in range(len(ka)):
	if ka[_] == 0:
		flag = 1
		break
if flag == 0:
	for i in range(n):
		if l[i] == 1:
			ma_flag = 0
			z1 = i - r + 2
			z2 = i + r
			z1 = max(1, z1)
			z2 = min(n, z2)
			for i in range(z1 - 1, z2):
				if ka[i] == 1:
					ma_flag = 1
			if ma_flag == 1:
				count += 1
			else:
				for i in range(z1 - 1, z2):
					ka[i] -= 1
	print(count)
else:
	print(-1)


from sys import exit
(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
intervals = []
for i in range(n):
	if arr[i] != 1:
		continue
	pos = i
	left = max(0, i - r + 1)
	right = min(n - 1, i + r - 1)
	intervals.append([left, right])
p = 0
res = 0
while p < n:
	good = list(filter(lambda interv: interv[0] <= p <= interv[1], intervals))
	if not good:
		print(-1)
		exit()
	best = max(good, key=lambda interv: interv[1])
	p = best[1] + 1
	res += 1
if p >= n:
	print(res)
else:
	print(-1)


import sys

def rint():
	return map(int, sys.stdin.readline().split())
(n, r) = rint()
a = list(rint())
cnt = 0
for i in range(n):
	if a[i] == 0 or a[i] == 1:
		for j in range(r - 1, -1, -1):
			if i + j < 0 or i + j >= n:
				continue
			if a[i + j] == 1 or a[i + j] == 3:
				cnt += 1
				for k in range(max(0, i + j - r + 1), min(n - 1, i + j + r - 1) + 1):
					if a[k] == 0:
						a[k] = 2
					if a[k] == 1:
						a[k] = 3
				break
		else:
			for j in range(0, r):
				if i - j < 0 or i - j >= n:
					continue
				if a[i - j] == 1 or a[i - j] == 3:
					cnt += 1
					for k in range(max(0, i - j - r + 1), min(n - 1, i - j + r - 1) + 1):
						if a[k] == 0:
							a[k] = 2
						if a[k] == 1:
							a[k] = 3
					break
			else:
				print(-1)
				exit()
print(cnt)


(n, r) = [int(x) for x in input().split()]
ns = [int(x) for x in input().split()]

def fin(i):
	p = need + r - 1
	last = max(need - r, -1)
	j = min(len(ns) - 1, p)
	while j > last:
		if ns[j] > 0:
			return j + r
		j -= 1
	return -1
need = 0
ans = 0
while need < len(ns):
	ans += 1
	need = fin(need)
	if need == -1:
		print(-1)
		quit()
print(ans)


(n, r) = map(int, input().split())
ar = [int(i) for i in input().split()]
ans = 0
ind = -1
while ind < n - 1:
	t = -10
	q = ind - r + 1
	q = max(q, -1)
	for i in range(n - 1, q, -1):
		if ar[i] and ind + r >= i:
			t = i
			ind = t + r - 1
			ans = ans + 1
			break
	if t < 0:
		ans = -1
		break
print(ans)


def mainA():
	T = int(input())
	for i in range(T):
		(L, v, l, r) = map(int, input().split())
		ans = L // v
		dow = l // v * v
		up = r // v * v
		if dow < l:
			dow += v
		ans -= max((up - dow) // v + 1, 0)
		print(ans)

def mainB():
	(n, r) = map(int, input().split())
	a = [int(e) for e in input().split()]
	r -= 1
	fr = 0
	ans = 0
	while fr < n:
		i = min(fr + r, n - 1)
		flag = False
		while i >= max(fr - r, 0) and (not flag):
			if a[i] == 1:
				ans += 1
				fr = i + r + 1
				flag = True
				break
			i -= 1
		if not flag:
			print(-1)
			return
	print(ans)
mainB()


(n, r) = input().split(' ')
heat = list(map(int, input().split(' ')))
n = int(n)
r = int(r)
if r is 1:
	if 0 in heat:
		ct = -1
	else:
		ct = n
elif r >= n:
	if 1 in heat:
		ct = 1
	else:
		ct = -1
else:
	r = r - 1
	ct = 0
	pos = -1
	posHeat = -1
	while posHeat < n - 1:
		it = posHeat + r + 1
		if it > n - 1:
			it = n - 1
		flag = -1
		for i in range(it, pos, -1):
			if heat[i] is 1:
				flag = 0
				ct = ct + 1
				posHeat = i + r
				if posHeat >= n - 1:
					flag = 1
					break
				pos = i
				break
		if flag is not 0:
			if flag is -1:
				ct = -1
			break
print(ct)


import math

def main():
	(n, r) = map(int, input().split())
	a = [0]
	a.extend(list(map(int, input().split())))
	p = [0 for _ in range(n + 2)]
	s = [0 for _ in range(n + 2)]
	cnt = 0
	for i in range(1, n + 1):
		if a[i] == 1:
			cnt += 1
			p[max(1, i - r + 1)] += 1
			p[min(n + 1, i + r)] -= 1
	for i in range(1, n + 1):
		s[i] = s[i - 1] + p[i]
		if s[i] == 0:
			print(-1)
			return
	for i in range(1, n + 1):
		if a[i] == 1:
			p[max(1, i - r + 1)] -= 1
			p[min(n + 1, i + r)] += 1
			for j in range(1, n + 1):
				s[j] = 0
			flag = True
			for j in range(1, n + 1):
				s[j] = s[j - 1] + p[j]
				if s[j] == 0:
					flag = False
					break
			if flag:
				cnt -= 1
			else:
				p[max(1, i - r + 1)] += 1
				p[min(n + 1, i + r)] -= 1
	print(cnt)
main()


R = lambda : map(int, input().split())
(n, r) = R()
a = [1] + [0] * (r - 1) + [*R()] + [0] * (r - 1)
c = p = 0
try:
	while p < n:
		p = next((i for i in range(p + 2 * r - 1, p, -1) if a[i]))
		c += 1
except:
	c = -1
print(c)


(n, r) = map(int, input().split())
t = list(map(int, input().split()))
arr = [0] * (n + 1)
for i in range(n):
	if t[i] == 1:
		arr[max(i - r + 1, 0)] += 1
		arr[min(n, i + r)] -= 1
for j in range(1, n + 1):
	arr[j] += arr[j - 1]
if 0 in arr[:n]:
	print(-1)
else:
	ans = 0
	for i in range(n):
		st = max(0, i - r + 1)
		en = min(i + r, n)
		h = 0
		for j in range(st, en):
			if arr[j] == 1:
				h += 1
		if h == 0:
			ans += 1
			for j in range(st, en):
				arr[j] -= 1
	print(sum(t) - ans)


(n, r) = map(int, input().strip().split())
l = list(map(int, input().strip().split()))
s = [0] * n
c = 0
while True:
	tmp = -1
	for j in range(c - r + 1, c + r):
		if j >= 0 and j < n and (l[j] == 1):
			tmp = j
	if tmp == -1:
		print(-1)
		exit(0)
	s[tmp] = 1
	c = tmp + r
	if c >= n:
		break
print(sum(s))


from bisect import bisect_right
(n, r) = map(int, input().split())
t = list(map(int, input().split()))
t_pos = []
wyn = 0
for x in range(0, len(t), +1):
	if t[x] == 1:
		t_pos.append(x)
if len(t_pos) == 0:
	print('-1')
	exit(0)
if r == 1:
	if len(t_pos) == n:
		print(n)
		exit(0)
	else:
		print('-1')
		exit(0)
if t_pos[0] > r - 1 or n - t_pos[-1] > r:
	print('-1')
	exit(0)
n_pos = 0
szuk_pos = 0
prev_pos = 0
while True:
	prev_pos = n_pos
	if n_pos == 0:
		szuk_pos = n_pos + r - 1
	else:
		szuk_pos = t_pos[n_pos - 1] + 2 * (r - 1) + 1
	n_pos = bisect_right(t_pos, szuk_pos)
	wyn += 1
	if t_pos[n_pos - 1] + r >= len(t):
		break
	if n_pos == prev_pos:
		print('-1')
		exit(0)
print(wyn)


(n, r) = map(int, input().split())
s = [int(x) for x in input().split()]
ptr = 0
c = 1
temp = 0
lst = 0
ct = 0
ans = 0
while ptr < n:
	if ptr == n - 1 and c > 0:
		ptr = lst
		c = r
	if c == r and s[ptr] == 1:
		c = -r + 2
		ptr = ptr + 1
		ans = ans + 1
	elif c == r and s[ptr] != 1:
		ptr = lst
		c = r
	else:
		ptr = ptr + 1
		c = c + 1
	if ptr < n:
		if s[ptr] == 1:
			lst = ptr
	ct = ct + 1
	if ct > 100000:
		temp = 1
		break
if temp == 0:
	print(ans)
else:
	print('-1')


def heaters(n, r, arr):
	ultimo = -1
	con = 0
	n = n - 1
	while ultimo < n:
		inicio = -1
		encontrado = False
		mid = max(-1, ultimo - r + 1)
		for i in range(n, mid, -1):
			if arr[i] == 1:
				if i - r <= ultimo:
					if i + r - 1 > inicio:
						inicio = i
						encontrado = True
						break
		if not encontrado:
			return -1
		con = con + 1
		ultimo = inicio + r - 1
	return con
(n, r) = [int(c) for c in input().split()]
arr = [int(c) for c in input().split()]
print(heaters(n, r, arr))


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = last = 0
while True:
	pos = -1
	for i in range(last + r - 1, last - r, -1):
		if i < 0 or i >= n:
			continue
		if a[i] == 1:
			pos = i
			break
	if pos == -1:
		print(-1)
		exit()
	ans += 1
	last = pos + r
	if last >= n:
		break
print(ans)


(n, r) = map(int, input().split())
arr = [int(x) for x in input().split()]
c = 0
r = min(n, r)
f = False
i = 0
area = 0
while i < n:
	if area >= n:
		print(c)
		break
	if c == 0:
		for k in range(r - 1, -1, -1):
			if arr[i + k]:
				area = i + k + r
				i += k + 1
				c += 1
				break
		else:
			print(-1)
			break
	else:
		for k in range(min(n - 1, (r - 1) * 2), -1, -1):
			if i + k >= n:
				f = True
				continue
			if arr[i + k]:
				area = i + k + r
				i += k + 1
				c += 1
				break
		else:
			print(c if area >= n else -1)
			break
else:
	print(c if c != 0 else -1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))

def searchr(st):
	loop = 2 * r - 2
	while loop >= 0:
		if a[st + loop] == 1:
			break
		loop = loop - 1
	return loop
if r >= n:
	C = sorted(a, reverse=True)
	if C[0] == 0:
		print(-1)
	else:
		print(1)
else:
	start = 0
	count = 0
	test = r - 1
	while test >= 0:
		if a[start + test] == 1:
			start = start + test + 1
			count = count + 1
			break
		test = test - 1
	if test == -1:
		count = -1
		print(count)
	else:
		while start + 2 * r - 2 <= n - 1:
			flag = searchr(start)
			if flag == -1:
				count = -1
				break
			else:
				count = count + 1
				start = start + flag + 1
		if count == -1:
			print(count)
		elif n - 1 < start + r - 1:
			print(count)
		else:
			B = sorted(a[n - r:n], reverse=True)
			if B[0] == 0:
				print(-1)
			else:
				count = count + 1
				print(count)


from sys import stdin
(n, m) = map(int, input().split())
s = [-1] + list(map(int, stdin.readline().strip().split()))
dp = [[10 ** 4 for i in range(2)] for j in range(n + 1)]
dp[0][0] = 0
dp[0][1] = 0
for i in range(1, n + 1):
	if s[i] == 1:
		dp[i][1] = min(dp[max(i - m, 0)][0] + 1, dp[max(i - m, 0)][1] + 1)
		for j in range(i + 1, min(n + 1, i + m)):
			dp[j][0] = min(dp[j][0], dp[i][1])
		for j in range(i - 1, max(-1, i - m), -1):
			dp[j][0] = min(dp[j][0], dp[i][1])
x = min(dp[-1])
if x == 10000:
	print(-1)
else:
	print(x)


def get_max(x, y):
	if x > y:
		return x
	else:
		return y

def get_min(x, y):
	if x < y:
		return x
	else:
		return y
seg = []
(n, r) = map(int, input().split())
ar = list(map(int, input().split()))
for i in range(len(ar)):
	if ar[i] == 0:
		continue
	seg.append((get_max(0, i - r + 1), -get_min(i + r - 1, n - 1)))
seg.sort()
if len(seg) == 0:
	print(-1)
elif seg[0][0] != 0:
	print(-1)
else:
	(R, tmpR) = (-seg[0][1], -1)
	hasil = int(1)
	for i in range(1, len(seg)):
		if seg[i][0] > R + 1:
			R = tmpR
			hasil = hasil + 1
			tmpR = -1
			if seg[i][0] > R + 1:
				hasil = -1
				break
		if -seg[i][1] > R and -seg[i][1] > tmpR:
			tmpR = -seg[i][1]
	if tmpR != -1:
		R = tmpR
		hasil = hasil + 1
	if R != n - 1:
		hasil = -1
	print(hasil)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
ais = list(map(int, input().split()))

def f(ais, k):
	if sum(ais) == 0:
		return -1
	pos = [i for i in range(len(ais)) if ais[i]]
	last = -1
	ans = 0
	j = 0
	while last < len(ais) - 1:
		p = -1
		while j < len(pos) and pos[j] - k <= last:
			p = j
			j += 1
		if p == -1:
			return -1
		last = pos[p] + k - 1
		ans += 1
	return ans if last >= n - 1 else -1
print(f(ais, k))


def go():
	(n, r) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	c = 0
	last = -1
	while last < n - 1:
		pos = -1
		for i in range(n - 1, max(-1, last - r + 1), -1):
			if a[i] == 1 and i - r <= last:
				pos = i
				break
		if pos == -1:
			return -1
		c += 1
		last = pos + r - 1
	return c
print(go())


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
for i in range(n):
	if a[i] == 1:
		if i - r + 1 < 0:
			c = 0
		else:
			c = i - r + 1
		if i + r - 1 > n - 1:
			c1 = n - 1
		else:
			c1 = i + r - 1
		for j in range(c, c1 + 1):
			b[j] += 1
x = sum(a)
y = 15
z = 0
if min(b) == 0:
	print(-1)
else:
	for i in range(n):
		if a[i] == 1:
			if i - r + 1 < 0:
				c = 0
			else:
				c = i - r + 1
			if i + r - 1 > n - 1:
				c1 = n - 1
			else:
				c1 = i + r - 1
			for j in range(c, c1 + 1):
				if b[j] == 1:
					z += 1
			if z == 0:
				x -= 1
				for j in range(c, c1 + 1):
					b[j] -= 1
			z = 0
	print(x)


def mini(arr, n, k):
	lo = [0 for i in range(n + 1)]
	o = -1
	for i in range(n):
		if arr[i] == 1:
			o = i
		lo[i] = o
	a = 0
	i = 0
	while i < n:
		pos = lo[min(i + k - 1, n - 1)]
		if pos == -1 or pos + k <= i:
			return -1
		i = pos + k
		a += 1
	return a
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
print(mini(arr, n, k))


from collections import defaultdict

def main():
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	pos = 0
	ans = 0
	while pos < n:
		cooler = min(n - 1, pos + r - 1)
		while cooler >= max(0, pos - r + 1) and a[cooler] == 0:
			cooler -= 1
		if cooler < max(0, pos - r + 1):
			ans = -1
			break
		else:
			ans += 1
			pos = cooler + r
	print(ans)
main()


(n, r) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
p = -1
ans = 0
while p < n - 1:
	found = False
	for i in range(n - 1, -1, -1):
		if a[i] == 1 and i - r + 1 <= p + 1 and (i + r - 1 > p):
			found = True
			p = i + r - 1
			break
	if not found:
		break
	ans += 1
if p < n - 1:
	print(-1)
else:
	print(ans)


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.insert(0, 0)
pos = 1
ans = 0
last = 0
while True:
	if pos > n:
		break
	prelast = last
	for i in range(max(0, pos - r + 1), min(pos + r, n + 1)):
		if a[i] == 1:
			pos = i + r
			last = i
	if prelast == last:
		ans = -1
		break
	else:
		ans += 1
print(ans)


a = input().split()
(n, r) = (int(a[0]), int(a[1]))
heaters = input().split()

def heat():
	indexes_1 = []
	for i in range(len(heaters)):
		if heaters[i] == '1':
			indexes_1.append(i)
	if len(indexes_1) == 0:
		return -1
	elif indexes_1[0] - r + 1 > 0:
		return -1
	elif indexes_1[-1] + r < len(heaters):
		return -1

	def find_start():
		finding_index = r - 1
		found_index = None
		for i in range(len(indexes_1)):
			if indexes_1[i] <= finding_index:
				found_index = i
			else:
				break
		return found_index
	first = find_start()
	count = 1
	while first < len(indexes_1):
		if indexes_1[first] + r >= len(heaters):
			break
		finding_index = indexes_1[first] + 2 * (r - 1) + 1
		second = first + 1
		found_index = None
		while second < len(indexes_1):
			if indexes_1[second] <= finding_index:
				found_index = indexes_1[second]
				second += 1
			else:
				break
		if found_index is None:
			return -1
		else:
			first = second - 1
		count += 1
	return count
print(heat())


(n, b) = map(int, input().split())
arr = list(map(int, input().split()))
i = -1
j = b - 1
if j >= n:
	j = n - 1
flag = 0
count = 0
while j < n:
	while j > i:
		if arr[j] == 1:
			i = j
			j += 2 * b - 1
			count += 1
			break
		else:
			j -= 1
	if j - b >= n - 1:
		break
	if j > n - 1:
		j = n - 1
	if i == n - 1:
		break
	if i == j:
		flag = 1
		break
if flag == 1:
	print(-1)
else:
	print(count)


(n, r) = map(int, input().split())
heaters = list(map(int, input().split()))
count = 0
position = 0
last_seen_heater = -1
while position < n:
	index = last_seen_heater + 1
	while index < position + r and index < n:
		if heaters[index] == 1:
			last_seen_heater = index
		index += 1
	new_pos = position
	if last_seen_heater >= 0:
		new_pos = last_seen_heater + r
	if new_pos != position:
		position = new_pos
		count += 1
	else:
		count = -1
		break
print(count)


(n, h_power) = list(map(int, input().strip().split()))
arr = [1] + [0] * (h_power - 1) + list(map(int, input().strip().split())) + [0] * (h_power - 1) + [1]
n = len(arr)
max_dist = 0
dist = 0
for num in arr:
	if num == 0:
		dist += 1
	else:
		dist = 0
	if dist > max_dist:
		max_dist = dist
if max_dist > (h_power - 1) * 2:
	print(-1)
else:
	heater_count = 0
	max_power_gap = (h_power - 1) * 2 + 1
	best_idx_so_far = 0
	last_idx = 0
	for idx in range(n - 1):
		if arr[idx] == 1:
			best_idx_so_far = idx
		if idx - last_idx == max_power_gap:
			heater_count += 1
			last_idx = best_idx_so_far
	print(heater_count)


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
i = 0
ok = True
ans = 0
while i < n:
	z = min(i + r - 1, n - 1)
	j = max(i - r + 1, 0)
	p = -1
	for k in range(z, j - 1, -1):
		if a[k] == 1:
			p = k
			break
	if p == -1:
		ok = False
		break
	ans += 1
	i = p + r
if ok:
	print(ans)
else:
	print(-1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ind = []
for i in range(len(a)):
	if a[i] == 1:
		ind.append(i)
ans = [0] * len(a)
for i in ind:
	for j in range(max(i - r, -1) + 1, min(i + r, len(a))):
		ans[j] += 1
if 0 in ans:
	print(-1)
else:
	c = len(ind)
	for i in ind:
		tag = False
		for j in range(max(i - r, -1) + 1, min(i + r, len(a))):
			if ans[j] == 1:
				tag = True
			ans[j] -= 1
		if tag:
			for j in range(max(i - r, -1) + 1, min(i + r, len(a))):
				ans[j] += 1
		else:
			c -= 1
	print(c)


(n, r) = map(int, input().split())
A = list(map(int, input().split()))
imos = [0] * (n + 1)
for i in range(n):
	if A[i] == 0:
		continue
	imos[max(0, i - r + 1)] += 1
	imos[min(i + r - 1 + 1, n)] -= 1
from itertools import accumulate
imos = list(accumulate(imos))
for i in range(n):
	if imos[i] == 0:
		print(-1)
		exit()
cnt = sum(A)
for i in range(n):
	p = max(0, i - r + 1)
	q = min(i + r - 1 + 1, n)
	for j in range(p, q):
		if imos[j] == 1:
			break
	else:
		cnt -= 1
		for j in range(p, q):
			imos[j] -= 1
print(cnt)


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import collections
import itertools
import bisect
import heapq
import random

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	i = 2
	while i * i <= n:
		if primes[i] == True:
			for j in range(i * i, n + 1, i):
				primes[j] = False
		i += 1
	pr = []
	for i in range(0, n + 1):
		if primes[i]:
			pr.append(i)
	return pr

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
(n, r) = map(int, input().split())
l = list(map(int, input().split()))
eff = [0] * (n + 1)
for i in range(0, n):
	if l[i] == 1:
		sp = max(0, i - (r - 1))
		lp = min(n - 1, i + (r - 1))
		eff[sp] += 1
		eff[lp + 1] -= 1
for i in range(1, n + 1):
	eff[i] += eff[i - 1]
if min(eff[:n]) <= 0:
	print(-1)
else:
	ans = l.count(1)
	for i in range(0, n):
		if l[i] == 1:
			sp = max(0, i - (r - 1))
			lp = min(n - 1, i + (r - 1))
			if min(eff[sp:lp + 1]) > 1:
				for j in range(sp, lp + 1):
					eff[j] -= 1
				ans -= 1
	print(ans)


(n, r) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
count = 0
start = 0
while start < n:
	pos = -1
	for i in range(start + r - 1, start - r, -1):
		if i < 0 or i > n - 1:
			continue
		if arr[i] == 1:
			pos = i
			break
	if pos == -1:
		print(-1)
		exit()
	count += 1
	start = pos + r
print(count)


[n, r] = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
last_heater = None
heaters = n * [0]
last_looked = None
ok = False
r = r - 1
last_looked = min(r + 1, n)
for i in reversed(range(0, min(r + 1, n))):
	if a[i] == 1:
		heaters[i] = 1
		last_heater = i
		ok = True
		break
if last_heater == None:
	print(-1)
else:
	while last_heater < n - r - 1:
		maximum = last_heater + 2 * r + 1
		ok = False
		for i in reversed(range(last_looked, min(n, maximum + 1))):
			last_looked = min(n, maximum + 1)
			if a[i] == 1:
				heaters[i] = 1
				last_heater = i
				ok = True
				break
		if not ok:
			print(-1)
			break
if ok:
	print(sum(heaters))


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
result = 0
i = 0
while i < len(a):
	b = True
	k = i
	for j in range(min(n - 1, k + r - 1), max(0, k - r + 1) - 1, -1):
		if a[j] == 1:
			i = j + r
			result += 1
			b = False
			break
	if b:
		break
if not b:
	print(result)
else:
	print(-1)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
new = [-1] * 1010
for i in range(len(arr)):
	if arr[i] == 0:
		continue
	else:
		for j in range(max(0, i - k + 1), min(n - 1, i + k - 1) + 1):
			new[j] = max(new[j], i)
pos = 0
ans = 0
while pos < n:
	if new[pos] == -1:
		ans = -1
		break
	ans += 1
	pos = new[pos] + k
print(ans)


from collections import defaultdict
(n, r) = map(int, input().split())
a = list(map(int, input().split()))
lr = []
d = defaultdict(list)
for i in range(n):
	if a[i] == 1:
		li = max(0, i - r + 1)
		ri = min(n - 1, i + r - 1)
		lr.append((li, ri))
		for j in range(li, ri + 1):
			d[j].append(len(lr) - 1)
now = 0
ans = 0
while now < n:
	if len(d[now]) == 0:
		print(-1)
		exit()
	now = lr[d[now][-1]][1] + 1
	ans += 1
print(ans)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
if r == 1:
	for e in a:
		if e == 0:
			print(-1)
			break
	else:
		print(n)
elif r < n:
	rm1 = r - 1
	ci = rm1
	c = 0
	lasthit = -1
	flag = True
	while ci < n:
		if a[ci] == 1:
			lasthit = ci
			c += 1
			ci += 2 * r - 1
			if ci > n - 1:
				if lasthit + r > n - 1:
					continue
				else:
					ci = n - 1
		else:
			ci -= 1
			if ci == lasthit:
				flag = False
				print(-1)
				break
	if flag:
		print(c)
elif 1 in a:
	print(1)
else:
	print(-1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
i = 0
cnt = 1
flag = 1
k = 0
for i in range(min(n, r)):
	if a[i] == 1:
		flag = 0
		k = i
i = k
if flag:
	print(-1)
else:
	while i + r - 1 < n - 1:
		flag = 1
		for j in range(i + 1, i + 2 * r):
			if j < n:
				if a[j] == 1:
					i = j
					flag = 0
		cnt += 1
		if flag:
			break
	if flag:
		print(-1)
	else:
		print(cnt)


(n, r) = map(int, input().split())
lst = list(map(int, input().split()))
dp = [0 for i in range(n)]
for pos in range(n):
	if lst[pos] == 1:
		for j in range(max(0, pos - r + 1), min(n, pos + r)):
			dp[j] += 1
if 0 in dp:
	print(-1)
else:
	ans = lst.count(1)
	for pos in range(n):
		if lst[pos] == 1:
			flag = True
			for j in range(max(0, pos - r + 1), min(n, pos + r)):
				if dp[j] == 1:
					flag = False
			if flag:
				ans -= 1
				for j in range(max(0, pos - r + 1), min(n, pos + r)):
					dp[j] -= 1
	print(ans)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
b = [True] * n
count = 0
for i in range(n):
	if b[i]:
		f = -1
		for j in range(r):
			if j + i == n:
				break
			if a[i + j] == 1:
				f = i + j
		if f == -1:
			for j in range(min(r, i + 1)):
				if a[i - j] == 1:
					f = i - j
					break
		if f == -1:
			print(-1)
			exit(0)
		for j in range(max(f - r + 1, 0), min(f + r, n)):
			b[j] = False
		count += 1
print(count)


(n, r) = map(int, input().split())
a = list(map(lambda c: bool(int(c)), input().split()))
c = []
for i in range(n):
	if a[i]:
		c.append((max(i - r + 1, 0), min(i + r - 1, n - 1)))
if len(c) == 0:
	print(-1)
else:
	key = not (c[0][0] == 0 and c[-1][1] == n - 1)
	for i in range(len(c) - 1):
		if c[i][1] < c[i + 1][0] - 1:
			key = True
			break
	if key:
		print(-1)
	else:
		i = 0
		while i < len(c) and c[i][0] == 0:
			i += 1
		s = [c[i - 1]]
		for i in range(i, len(c)):
			if c[i][0] - 1 > s[-1][1]:
				s.append(c[i - 1])
		if s[-1][1] != n - 1:
			s.append(0)
		print(len(s))


(n, r) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0] * n
for i in range(n):
	if a[i] == 1:
		if i - (r - 1) < 0:
			b[0] += 1
		else:
			b[i - (r - 1)] += 1
		if i + r < n:
			b[i + r] += -1
for i in range(1, n):
	b[i] += b[i - 1]
if b.count(0) == 0:
	l = 0
	for i in range(n):
		if a[i] == 1:
			if i - (r - 1) < 0:
				p = 0
			else:
				p = i - (r - 1)
			if i + r < n:
				q = i + r
			else:
				q = n
			t = 0
			while p < q:
				if b[p] == 1:
					t += 1
					break
				p += 1
			if t == 1:
				l += 1
			else:
				if i - (r - 1) < 0:
					p = 0
				else:
					p = i - (r - 1)
				while p < q:
					b[p] = b[p] - 1
					p += 1
	print(l)
else:
	print(-1)


(n, r) = map(int, input().split())
l = list(map(int, input().split()))
num = 0
boo = False
last = 0
count = 0
if r >= n:
	if l.count(1) == 0:
		print(-1)
	else:
		print(1)
	exit()
for i in range(r):
	if l[i] == 1:
		count += 1
		last = i
if count == 0:
	print(-1)
	exit()
num += count - 1
i = last
while i < n:
	count = 0
	for j in range(1, 2 * r):
		if i + j >= n:
			boo = True
			break
		if l[i + j] == 1:
			count += 1
			last = j
	if not boo and count == 0:
		print(-1)
		exit()
	if boo:
		if j <= r:
			num += count
		else:
			if j - last > r:
				print(-1)
				exit()
			num += max(count - 1, 0)
		break
	num += max(count - 1, 0)
	i += last
	last = 0
print(l.count(1) - num)


(n, r) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
count = 0
i = 0
while i < n:
	right = min(n - 1, i + r - 1)
	left = max(0, i - r + 1)
	flag = 0
	for j in range(right, left - 1, -1):
		if a[j] == 1:
			start = j
			flag = 1
			break
	if not flag:
		break
	count += 1
	i = start + r
if flag:
	print(count)
else:
	print(-1)


(n, r) = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
b = [0] * n
ans = 0
for i in range(n):
	if b[i] == 0:
		found = False
		for j in range(min(n - 1, i + r - 1), max(-1, i - r), -1):
			if a[j] == 1:
				for k in range(min(n - 1, j + r - 1), max(-1, j - r), -1):
					b[k] = 1
				ans += 1
				found = True
				break
		if not found:
			ans = -1
			break
print(ans)


(n, r) = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
last = -1
while last < n - 1:
	pos = -1
	for i in range(n - 1, max(-1, last - r + 1), -1):
		if a[i] == 1 and i - r <= last:
			pos = i
			break
	if pos == -1:
		print(-1)
		exit()
	ans += 1
	last = pos + r - 1
print(ans)


(n, r) = (int(i) for i in input().split())
count = 0
arr = []
br = 0
for i in input().split():
	arr.append([0, int(i)])
for i in range(n):
	cur = arr[i]
	if cur[0] == 0:
		maxind = -1
		for j in range(max(i - r, 0), min(i + r, n)):
			if arr[j][1] == 1:
				maxind = j
		if maxind == -1:
			br = 1
			break
		arr[maxind][1] = 2
		count += 1
		for j in range(max(maxind - r, 0), min(maxind + r, n)):
			arr[j][0] = 1
if br:
	count = -1
print(count)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
x = r - 1
b = 0
for m in range(min(x, n - 1), -1, -1):
	if a[m] == 1:
		i = m
		b = 1
		break
if b == 0:
	s = -1
else:
	s = 1
	while i + x < n - 1:
		j = i + 1
		b = 0
		for l in range(min(j + 2 * x, n - 1), j - 1, -1):
			if a[l] == 1:
				b = 1
				k = l
				break
		if b == 0:
			s = -1
			break
		else:
			s += 1
			i = k
print(s)


def count_col(inp_ar, n, r):
	res = 0
	last = -1
	while last < n - 1:
		Flag = False
		for i in list(reversed(range(max(0, last - r + 2), min(n, last + r + 1)))):
			if int(inp_ar[i]) == 1:
				last = i + r - 1
				res += 1
				Flag = True
				break
		if not Flag:
			return -1
		else:
			Flag = False
	return int(res)
temp = input().split()
n = int(temp[0])
r = int(temp[1])
inp_ar = input().split()
print(count_col(inp_ar, n, r))


(n, r) = map(int, input().strip().split())
arr1 = list(map(int, input().strip().split()))
arr = [0] * n
ans = 0
f = 0
for i in range(n):
	f1 = 0
	f2 = 0
	ind = -1
	if arr[i] == 0:
		for j in range(min(n - 1, i + r - 1), i - 1, -1):
			if arr1[j] == 1 and f1 == 0:
				ans += 1
				ind = j
				f1 = 1
				arr[j] = 2
			elif f1 == 1:
				arr[j] = 2
		if f1 == 0:
			for j in range(i - 1, max(0, i - r + 1) - 1, -1):
				if arr1[j] == 1 and f2 == 0:
					ans += 1
					f2 = 1
					arr[j] = 2
					ind = j
				elif f2 == 1:
					arr[j] = 2
		if ind != -1:
			for j in range(ind, min(n, ind + r)):
				if arr[j] == 0:
					arr[j] = 2
		if f2 == 0 and f1 == 0:
			f = 1
			break
if f == 1:
	print(-1)
else:
	print(ans)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
k = -1
for i in range(n):
	if a[i] == 1:
		if i - r > k:
			ans = 0
			break
		tmp = 0
		for j in range(i, n):
			if a[j] == 1:
				if j - r <= k:
					tmp = j + r - 1
				else:
					break
		ans += 1
		k = tmp
		if k >= n - 1:
			break
if ans and k >= n - 1:
	print(ans)
else:
	print(-1)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
cur = 0
res = 0
while cur < n:
	b = max(0, cur - r + 1)
	c = a[b:cur + r]
	if sum(c):
		i = len(c) - c[-1::-1].index(1) - 1
		cur = b + i + r
		res += 1
	else:
		print(-1)
		break
else:
	print(res)


(n, r) = map(int, input().split())
ar = [0] * r + list(map(int, input().split())) + [0] * (r + 2)
L = R = -1
f = 0
bn = 5
for i in range(2 * r - 1, r - 1, -1):
	if ar[i] == 1:
		L = i
		break
for i in range(n, n + r):
	if ar[i] == 1:
		R = i
		break
if L == -1 or R == -1:
	print('-1')
elif L >= R:
	print('1')
else:
	f = 2
	for i in range(L + 1, R):
		h = -1
		if L + r + r - 1 >= R:
			print(f)
			bn = 3
			break
		for j in range(L + 1, L + r + r):
			if ar[j] == 1:
				h = j
		if h == -1:
			print('-1')
			bn = 3
			break
		else:
			L = h
			f += 1
	if bn == 5:
		print(f)


(n, r) = map(int, input().split())
li = [int(i) for i in input().split()]
res = 1
x = -1
for i in range(min(n - 1, r - 1), -1, -1):
	if li[i] == 1:
		x = i
		break
else:
	print(-1)
	exit()
while x + r - 1 < n - 1:
	for i in range(min(n - 1, x + 2 * r - 1), x, -1):
		if li[i] == 1:
			x = i
			res += 1
			break
	else:
		print(-1)
		exit()
print(res)


(n, r) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	if a[i] == 1:
		b.append([max(0, i - r + 1), min(n - 1, i + r - 1)])
x = -1
k = 0
j = -1
ok = True
while x != n - 1:
	i = 0
	while i <= len(b) - 1 and b[i][0] <= x + 1:
		i += 1
	i -= 1
	if i == j:
		print(-1)
		ok = False
		break
	j = i
	k += 1
	x = b[i][1]
if ok:
	print(k)


(n, r) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = [0] * n
for i in range(n):
	if arr[i] == 1:
		for j in range(i, max(i - r, -1), -1):
			arr1[j] += 1
		for j in range(i + 1, min(i + r, n)):
			arr1[j] += 1
if 0 in arr1:
	print(-1)
else:
	count = arr.count(1)
	for i in range(n):
		if arr[i] == 1:
			flag = 0
			for j in range(i, max(i - r, -1), -1):
				if arr1[j] == 1:
					flag = 1
			for j in range(i, min(i + r, n)):
				if arr1[j] == 1:
					flag = 1
			if flag == 0:
				for j in range(i, max(i - r, -1), -1):
					arr1[j] -= 1
				for j in range(i + 1, min(i + r, n)):
					arr1[j] -= 1
				count -= 1
	print(count)


(n, r) = tuple(map(int, input().split()))
arr = list(map(int, input().split()))
(i, j) = (0, 0)
last_heater = -1
heaters_on = 0
while j < n:
	if arr[j] == 1:
		last_heater = j
	if i == j - r + 1:
		heaters_on += 1
		if last_heater == -1:
			print(-1)
			exit()
		i = last_heater + r
		j = j + 1
		last_heater = -1
	else:
		j += 1
if i >= n:
	print(heaters_on)
elif last_heater != -1:
	if last_heater + r - 1 >= n - 1:
		print(heaters_on + 1)
	else:
		print(-1)
else:
	print(-1)


p = list(map(int, input().split()))
n = p[0]
m = p[1]
a = list(map(int, input().split()))
c = {}
l = int(0)
r = int(0)
ans = int(0)
flag = int(0)
for i in range(0, n):
	c[i] = 0
while l < n:
	if c[l] == 1:
		l = l + 1
		continue
	ff = int(0)
	ans = ans + 1
	for i in range(l, min(n, l + m)):
		if a[i] == 1:
			ff = 1
			r = i + m
	if ff == 0:
		for i in range(max(0, l - m + 1), l):
			if a[i] == 1:
				ff = 1
				r = i + m
	if ff == 0:
		flag = 1
		break
	for i in range(l, r):
		c[i] = 1
	l = r
if flag == 1:
	print(-1)
else:
	print(ans)


(n, r1) = map(int, input().split())
a = list(map(int, input().split()))
right = -1
currentRight = -1
free = r1
c = 0
total = 0
(finish, stop) = (0, 0)
idex = 0
lastIdex = -1
while idex < n and free:
	free -= 1
	if a[idex] == 1:
		lastIdex = idex
		right = idex + r1 - 1
		c += 1
		if right >= n - 1:
			finish = 1
			total += 1
			break
	idex += 1
	if not free:
		if c > 0:
			total += 1
			c = 0
			free = r1 * 2 - 1
			idex = lastIdex + 1
		else:
			stop = 1
			break
if finish:
	print(total)
else:
	print(-1)