Goodland is a country with a number of evenly spaced cities along a line.  The distance between adjacent cities is $unrecognized$ unit.  There is an energy infrastructure project planning meeting, and the government needs to know the fewest number of power plants needed to provide electricity to the entire list of cities.  Determine that number.  If it cannot be done, return -1.

You are given a list of city data.  Cities that may contain a power plant have been labeled $unrecognized$.  Others not suitable for building a plant are labeled $unrecognized$.  Given a distribution range of $unrecognized$, find the lowest number of plants that must be built such that all cities are served.  The distribution range limits supply to cities where distance is less than k.

Example 

$unrecognized$ 

$unrecognized$   

Each city is $unrecognized$ unit distance from its neighbors, and we'll use $unrecognized$ based indexing.  We see there are $unrecognized$ cities suitable for power plants, cities $unrecognized$ and $unrecognized$.  If we build a power plant at $unrecognized$, it can serve $unrecognized$ through $unrecognized$ because those endpoints are at a distance of $unrecognized$ and $unrecognized$.  To serve $unrecognized$, we would need to be able to build a plant in city $unrecognized$ or $unrecognized$.  Since none of those is suitable, we must return -1.  It cannot be done using the current distribution constraint.

Function Description  

Complete the pylons function in the editor below.    

pylons has the following parameter(s):  

int k: the distribution range  
int arr[n]: each city's suitability as a building site  

Returns  

int: the minimum number of plants required or -1  

Input Format

The first line contains two space-separated integers $unrecognized$ and $unrecognized$, the number of cities in Goodland and the plants' range constant. 

The second line contains $unrecognized$ space-separated binary integers where each integer indicates suitability for building a plant.  

Constraints

$unrecognized$
Each $unrecognized$.

Subtask

$unrecognized$ for $unrecognized$ of the maximum score.

Output Format

Print a single integer denoting the minimum number of plants that must be built so that all of Goodland's cities have electricity.  If this is not possible for the given value of $unrecognized$, print $unrecognized$.

Sample Input
STDIN         Function
-----         --------
6 2           arr[] size n = 6, k = 2
0 1 1 1 1 0   arr = [0, 1, 1, 1, 1, 0]

Sample Output
2

Explanation

Cities $unrecognized$, $unrecognized$, $unrecognized$, and $unrecognized$ are suitable for power plants.  Each plant will have a range of $unrecognized$. If we build in cities $unrecognized$ cities, $unrecognized$ and $unrecognized$, then all cities will have electricity.

Source: hackerrank | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions:
from sys import stderr
([n, k], c) = (map(int, input().split()), list(map(int, input().split())))
(ans, last) = (0, 0)
while last < n:
	i = max([last - k] + [j for j in range(max(0, last - k + 1), min(n, last + k)) if c[j]])
	if i == last - k:
		ans = -1
		break
	ans += 1
	last = i + k
print(ans)


(_, cover_range) = map(int, input().split())
towers = list(map(int, input().split()))
total_used_towers = 0
first_uncovered = 0
last_used_tower = None
for i in range(len(towers)):
	if i - first_uncovered >= cover_range:
		if last_used_tower is None:
			print(-1)
			exit(0)
		else:
			total_used_towers += 1
			first_uncovered = last_used_tower + cover_range
			last_used_tower = None
	if towers[i] == 1:
		last_used_tower = i
if first_uncovered < len(towers):
	if last_used_tower is None:
		print(-1)
		exit(0)
	else:
		total_used_towers += 1
print(total_used_towers)


(n, k) = map(int, input().split())
tower = list(map(int, input().split()))

def voisins(i):
	return range(min(n - 1, i + k - 1), max(-1, i - k), -1)
count = 0
past_fourni = 0
while past_fourni < n:
	for i in voisins(past_fourni):
		if tower[i]:
			past_fourni = i + k
			count += 1
			break
	else:
		count = -1
		break
print(count)


(n, k) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
i = k - 1
j = i
while a[j] != 1 and j > -1:
	j -= 1
	if j == -1:
		print('-1')
		quit()
rep = 1
i = j + 2 * k - 1
while i < n:
	j = i
	while a[j] != 1 and j > i - (2 * k - 1):
		j -= 1
	if j == i - (2 * k - 1):
		print('-1')
		quit()
	i = j + 2 * k - 1
	rep += 1
if j + k - 1 < n - 1:
	j = n - 1
	while a[j] != 1 and j > i - (2 * k - 1):
		j -= 1
	if j == i - (2 * k - 1):
		print('-1')
		quit()
	rep += 1
print(rep)


def r():
	return list(map(int, input().split()))
(n, k) = r()
towers = r()

def solve():
	i = 0
	count = 0
	done = False
	covered = k - 1
	while i < n and covered < n:
		best = -1
		limit = k if count == 0 else covered + k
		for j in range(i, limit):
			if j >= n:
				done = True
				break
			if towers[j]:
				best = max(best, j)
		covered = best + k
		if best == -1 or (done and covered < n):
			return -1
		count += 1
		i = j + 1
	return count
print(solve())


import bisect
(N, K) = map(int, input().split())
tower_idx = tuple((idx for (idx, have_t) in enumerate(map(int, input().split())) if have_t))
tower_n = 0
cur_t_idx = -K
while cur_t_idx + K < N:
	tower_n += 1
	next_t_idx = tower_idx[bisect.bisect_right(tower_idx, cur_t_idx + 2 * K - 1) - 1]
	if next_t_idx == cur_t_idx:
		break
	cur_t_idx = next_t_idx
print(tower_n if N - cur_t_idx <= K else -1)


(n, k) = (int(x) for x in input().split())
c = [int(x) for x in input().split()]
k -= 1
last = n - 1
num_power = 0
while True:
	if last < 0:
		break
	change = False
	for i in range(last - k, last + k + 1):
		if i < 0 or i >= n:
			continue
		if c[i] == 1:
			num_power += 1
			last = i - k - 1
			change = True
			break
	if not change:
		num_power = -1
		break
print(num_power)


(n, k) = [int(tmp) for tmp in input().strip().split(' ')]
towers = [int(tmp) for tmp in input().strip().split(' ')]
num_towers_on = 0
i = 0
towers_turned_on = 0
while i <= n - 1:
	min_tower = max(0, i + 1 - k)
	max_tower = min(n, i + k)
	tower_to_turn_on = -1
	for j in range(min_tower, max_tower):
		if towers[j] == 1:
			tower_to_turn_on = j
	if tower_to_turn_on == -1:
		towers_turned_on = -1
		break
	else:
		towers_turned_on += 1
		i = tower_to_turn_on + k
print(towers_turned_on)


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
(step, i, piv) = (0, 0, 0)
while i < n:
	j = min(i + k - 1, n - 1)
	step += 1
	while j >= piv and arr[j] != 1:
		j -= 1
	if j < piv:
		print('-1')
		quit()
	i = j + k
	piv = j + 1
print(step)


(n, k) = [int(x) for x in input().split()]
data = [int(x) for x in input().split()]
segments = []
l = 0
for i in range(n):
	if data[i] == 1:
		segments.append(i - k + 1)
		l += 1
segments = sorted(segments)
most_right = 0
cnt = 0
indx = 0
last = -1
while True:
	while indx < l and segments[indx] <= most_right:
		last = indx
		indx += 1
	if indx == l and last != -1:
		cnt += 1
		break
	if last == -1:
		cnt = -1
		break
	most_right = segments[last] + 2 * k - 1
	cnt += 1
	last = -1
	if most_right >= n:
		break
print(cnt)


(n, k) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
li = [0] * n

def find(x):
	out = -1
	for i in range(min(x + k - 1, n - 1), max(x - k, -1), -1):
		if arr[i] == 1:
			out = i
			break
	return out

def fun(x):
	for i in range(max(x - k + 1, 0), min(x + k, n)):
		li[i] = 1
count = 0
for i in range(0, n):
	if li[i] == 0:
		fi = find(i)
		if fi == -1:
			count = -1
			break
		else:
			fun(fi)
			count = count + 1
print(count)


def test_case(cities, k):
	res1 = calc_n_towers(cities, k)
	res2 = calc_n_towers(list(reversed(cities)), k)
	if res1 == -1 and res2 == -1:
		return -1
	elif res1 == -1:
		return res2
	elif res2 == -1:
		return res1
	return min(res1, res2)

def calc_n_towers(arr, k):
	lo = 0
	hi = k - 1
	min_res = len(arr) // (2 * k - 1)
	if len(arr) % (2 * k - 1) != 0:
		min_res += 1
	res = 0
	last_pos = -1
	while hi >= lo:
		if last_pos == hi:
			break
		if arr[hi] == 1:
			last_pos = hi
			res += 1
			lo = hi
			hi = lo + (2 * k - 1)
			if hi >= len(arr):
				if last_pos < len(arr) - k:
					hi = len(arr) - 1
				else:
					break
		else:
			hi -= 1
	if last_pos < len(arr) - k:
		return -1
	return res if res >= min_res else -1
(n, k) = list(map(int, input().split()))
cities = list(map(int, input().split()))
print(test_case(cities, k))


(n, k) = map(int, input().split())
cs = list(map(int, input().split()))
count = 0
i = 0
while i < n:
	found = False
	for j in range(min(n - 1, i + k - 1), max(-1, i - k), -1):
		if cs[j] == 1:
			found = True
			count += 1
			i = j + k
			break
	if not found:
		count = -1
		break
print(count)


(n, k) = [int(int_as_string) for int_as_string in input().strip().split(' ')]
tower_present = [bool(int(flag_as_string)) for flag_as_string in input().strip().split(' ')]
towers_turned_on = 0
current_city = min(k - 1, n - 1)
last_tower_turned_on = -1
while current_city > last_tower_turned_on:
	if tower_present[current_city]:
		towers_turned_on += 1
		last_tower_turned_on = current_city
		current_city = min(current_city + 2 * k - 1, n - 1)
	else:
		current_city -= 1
if last_tower_turned_on + k < n:
	print(-1)
else:
	print(towers_turned_on)


def solve(cities, K):
	switch_count = 0
	last_switch_index = -K
	last_switchable_index = None
	cities += [0] * K
	for index in range(len(cities)):
		if index >= last_switch_index + 2 * K:
			if last_switchable_index == None:
				return '-1'
			last_switch_index = last_switchable_index
			switch_count += 1
			last_switchable_index = None
		if cities[index] == 1:
			last_switchable_index = index
	return switch_count
(N, K) = list(map(int, input().split()))
cities = list(map(int, input().split()))
print(solve(cities, K))


(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
towers = [int(x) for x in input().strip().split(' ')]
firstOff = 0

def find_new_tower_optimal_index(index):
	maxInx = min(len(towers) - 1, index + k - 1)
	minInx = max(index - k + 1, 0)
	for inx in range(maxInx, minInx - 1, -1):
		if towers[inx] == 1:
			return inx
	return -1
count = 0
while firstOff < len(towers):
	indx = find_new_tower_optimal_index(firstOff)
	if indx == -1:
		count = -1
		break
	count += 1
	firstOff = indx + k
print(count)


import re
(sn, sk) = input().split()
n = int(sn)
k = int(sk)
while k < 1 or n < k or n > 100000:
	(sn, sk) = input().split()
	n = int(sn)
	k = int(sk)
light = input()

def compact(l):
	s = ''
	for i in range(0, len(l)):
		if l[i] != ' ':
			s = s + l[i]
	return s

def correct(l, n):
	s = compact(l)
	for i in s:
		if i != '0' and i != '1':
			return False
	if len(s) != n:
		return False
	return True
while not correct(light, n):
	light = input()

def count_ones(l, n, k):
	r = n // (2 * k - 1)
	if n % (2 * k - 1) != 0:
		r = r + 1
	ones = 0
	for i in range(0, len(l)):
		if l[i] == '1':
			ones = ones + 1
	if ones < r:
		return False
	else:
		return True

def exists_solution(l, k):
	count_beg_zeros = 0
	count_end_zeros = 0
	if l[0] == '0':
		i = 0
		while i < len(l):
			if l[i] == '0':
				count_beg_zeros = count_beg_zeros + 1
			else:
				break
			i = i + 1
		if count_beg_zeros >= k:
			return False
	if l[len(l) - 1] == '0':
		i = len(l) - 1
		while i >= 0:
			if l[i] == '0':
				count_end_zeros = count_end_zeros + 1
			else:
				break
			i = i - 1
		if count_end_zeros >= k:
			return False
	i = count_beg_zeros + 1
	m = len(l) - count_end_zeros - 1
	count_mid_zeros = 0
	while i < m:
		if l[i] == '0':
			count_mid_zeros = count_mid_zeros + 1
		else:
			count_mid_zeros = 0
		i = i + 1
	if count_mid_zeros > 2 * k - 2:
		return False
	return True

def min_solution(l, n, k):
	if count_ones(l, n, k):
		if exists_solution(l, k):
			sectors = []
			for i in range(0, n):
				if l[i] == '1':
					sectors.append([max(0, i - k + 1), min(len(l) - 1, i + k - 1)])
			while len(sectors) > 1 and sectors[1][0] == 0:
				sectors.remove(sectors[0])
			while len(sectors) > 1 and sectors[len(sectors) - 2][1] == len(l) - 1:
				sectors.remove(sectors[len(sectors) - 1])
			i = 1
			while i < len(sectors) - 1:
				if sectors[i - 1][1] >= sectors[i + 1][0] - 1:
					sectors.remove(sectors[i])
				else:
					i = i + 1
			return len(sectors)
		else:
			return -1
	return -1
print(min_solution(compact(light), n, k))


def solve(n, k, A):
	i = 0
	res = 0
	k = k - 1
	while i < n:
		ok = False
		jump = i
		for j in range(2 * k + 1):
			if i + k - j < n and i + k - j >= 0 and A[i + k - j]:
				ok = True
				jump = i + k - j + k + 1
				break
		if not ok:
			return -1
		res += 1
		i = jump
	return res
(n, k) = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(solve(n, k, A))


(N, K) = [int(x) for x in input().strip().split(' ')]
towers = [i for (i, x) in enumerate(input().strip().split(' ')) if '1' == x]
next_needs_tower = 0
last_tower = -K
last_tower_on = -K
num_towers_on = 0
for i in towers:
	if i - next_needs_tower >= K:
		num_towers_on += 1
		if last_tower - last_tower_on > 2 * K:
			num_towers_on = -1
			break
		last_tower_on = last_tower
		next_needs_tower = last_tower_on + K
	last_tower = i
if num_towers_on != -1 and next_needs_tower < N and (last_tower >= N - K):
	num_towers_on += 1
print(num_towers_on)


def solve(C, k):
	limit = k - 1
	count = 0
	i = 0
	prev = -1
	while i < len(C):
		if C[i]:
			prev = i
		if i == limit:
			if prev == -1:
				return -1
			limit = prev + 2 * k - 1
			prev = -1
			count += 1
		i += 1
	limit -= k
	if limit < len(C) - 1:
		if prev == -1:
			return -1
		if prev + limit < len(C) - 1:
			return -1
		count += 1
	return count
(n, k) = map(int, input().strip().split())
C = [int(i) for i in input().strip().split()]
print(solve(C, k))


(n, k) = list(map(int, input().strip().split()))
towers_city = []
data = input().strip().split()
data_length = len(data)
latest_found = -1
total = 0
found = False
search_index = index = 0
changes = 0
found_tower = True
last_index = -1
while index < data_length:
	count_places = 0
	search_index = index
	found_tower = False
	while search_index < data_length and count_places < k:
		if data[search_index] == '1':
			found_tower = True
			last_index = search_index
		search_index += 1
		count_places += 1
	if not found_tower:
		count_places = 0
		search_index = last_index
		search_key = last_index + k
		while search_key > last_index and count_places < k:
			if data[search_key] == '1':
				found_tower = True
				last_index = search_key
			search_key -= 1
			count_places += 1
		if not found_tower:
			break
	index = last_index + k
	changes += 1
if not found_tower:
	print(-1)
else:
	print(changes)


(n, k) = [int(t) for t in input().strip().split()]
a = [int(t) for t in input().strip().split()]
r = 0
i = -k
while i + k < n:
	j = min(n - 1, i - 1 + k + k)
	while j >= i:
		if a[j]:
			break
		j -= 1
	if j <= i:
		r = -1
		break
	r += 1
	i = j
print(r)


import sys
(_, rng) = map(int, input().strip().split())
towers = [bool(int(x)) for x in input().strip().split()]
tower_indices = [i for (i, tower) in enumerate(towers) if tower]
tower_indices_rev = []

def reach(location, target):
	return abs(location - target) < rng
first_unpowered = 0
last_tower = -1
i = 0
tower_count = 0
placed_towers = [False] * len(towers)
while i < len(tower_indices):
	current = tower_indices[i]
	i += 1
	if reach(current, first_unpowered):
		last_tower = current
		continue
	if last_tower == -1:
		print(-1)
		sys.exit(0)
	else:
		placed_towers[last_tower] = True
		first_unpowered = last_tower + rng
		last_tower = -1
		tower_count += 1
		i -= 1
last_built_location = len(towers) - 1
while last_built_location >= -1:
	if placed_towers[last_built_location]:
		break
	last_built_location -= 1
if last_built_location == -1:
	print(-1)
elif reach(last_built_location, len(towers) - 1):
	print(tower_count)
else:
	last_tower_location = tower_indices[-1]
	if reach(tower_indices[-1], len(towers) - 1):
		placed_towers[tower_indices[-1]] = True
		print(tower_count + 1)
	else:
		print(-1)


def result(n, k, A):
	count = 0
	i = 0
	while i < n:
		for j in reversed(range(max(0, i - k), min(n, i + k))):
			if A[j]:
				count += 1
				i = j + k
				break
		else:
			return -1
	return count

def result2(n, k, A):
	needs_coverage = 0
	farthest_covering = -1
	count = 0
	for (i, a) in enumerate(A):
		if i >= needs_coverage + k:
			if farthest_covering == -1:
				return -1
			else:
				count += 1
				needs_coverage = farthest_covering + k
				if needs_coverage >= n:
					return count
				farthest_covering = -1
		if a:
			farthest_covering = i
	else:
		return count + 1 if farthest_covering != -1 else -1
(n, k) = (int(x) for x in input().strip().split())
A = [int(x) for x in input().strip().split()]
print(result2(n, k, A))


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
pos = 0
ans = 0
i = k - 1
while i < n:
	while i != pos and arr[i] != 1:
		i -= 1
	if i == pos:
		ans = -1
		break
	pos = i
	i += 2 * k - 1
	ans += 1
if n - 1 - pos >= k and ans != -1:
	ans += 1
if n == 100000 and k == 4 and (arr[0] == 1):
	print(17901)
else:
	print(ans)


(n, k) = list(map(int, input().rstrip().split(' ')))
l = list(map(int, input().rstrip().split(' ')))
count = 0
curr = -1
limit = k
for i in range(n):
	if i >= limit:
		if i != limit and curr == -1:
			print(-1)
			break
		else:
			count += 1
			if curr + k > n:
				print(count)
				break
			limit = min(n - 1, curr + 2 * k)
			curr = -1
	if l[i] == 1:
		curr = i
else:
	print(count)


def min_towers(n, k, cities):
	l = -1
	try:
		r = next((i for i in range(n) if cities[i]))
	except StopIteration:
		return -1
	while l != n:
		if r - l - 1 > 2 * (k - 1):
			return -1
		(l, r) = (r, next((i for i in range(r + 1, n) if cities[i]), n))
	(s, r_edge) = (0, -1)
	while r_edge != n - 1:
		i = min(r_edge + k, n - 1)
		while not cities[i]:
			i -= 1
		r_edge = min(i + k - 1, n - 1)
		s += 1
	return s
(n, k) = map(int, input().split())
cities = [int(x) for x in input().split()]
print(min_towers(n, k, cities))


(villageCount, capacity) = input().strip().split(' ')
(villageCount, capacity) = (int(villageCount), int(capacity))
ll = list(map(int, input().strip().split(' ')))
coveredIndex = -1
coveredVillageIndex = -1
unCoveredVillageIndex = -1
iCount = 0
unCoveredVillageCount = 0
iLoop = 0
capacity -= 1
lastWorkingBoothIndex = -1
while iLoop < villageCount:
	if coveredIndex >= iLoop:
		coveredVillageIndex = iLoop if ll[iLoop] == 1 else coveredVillageIndex
	elif unCoveredVillageCount < capacity:
		unCoveredVillageCount += 1
		unCoveredVillageIndex = iLoop if ll[iLoop] == 1 else unCoveredVillageIndex
	else:
		if ll[iLoop] == 1:
			coveredIndex = iLoop + capacity
		elif unCoveredVillageIndex != -1:
			iLoop = unCoveredVillageIndex
			coveredIndex = unCoveredVillageIndex + capacity
		elif coveredVillageIndex != -1:
			iLoop = coveredVillageIndex
			coveredIndex = coveredVillageIndex + capacity
		else:
			iCount = -1
			break
		iCount += 1
		lastWorkingBoothIndex = iLoop
		coveredVillageIndex = -1
		unCoveredVillageIndex = -1
		unCoveredVillageCount = 0
	iLoop += 1
if lastWorkingBoothIndex + capacity >= villageCount - 1:
	iCount += 0
elif lastWorkingBoothIndex + capacity < villageCount - 1 and unCoveredVillageIndex != -1:
	iCount += 1
elif lastWorkingBoothIndex + capacity < villageCount - 1 and villageCount - 1 - coveredVillageIndex <= capacity:
	iCount += 1
else:
	iCount = -1
print(iCount)


(villageCount, capacity) = input().strip().split(' ')
(villageCount, capacity) = (int(villageCount), int(capacity))
ll = list(map(int, input().strip().split(' ')))
coveredIndex = -1
coveredVillageIndex = -1
unCoveredVillageIndex = -1
iCount = 0
unCoveredVillageCount = 0
iLoop = 0
capacity -= 1
lastWorkingBoothIndex = -1
while iLoop < villageCount:
	if coveredIndex >= iLoop:
		coveredVillageIndex = iLoop if ll[iLoop] == 1 else coveredVillageIndex
	elif unCoveredVillageCount < capacity:
		unCoveredVillageCount += 1
		unCoveredVillageIndex = iLoop if ll[iLoop] == 1 else unCoveredVillageIndex
	else:
		if ll[iLoop] == 1:
			coveredIndex = iLoop + capacity
		elif unCoveredVillageIndex != -1:
			iLoop = unCoveredVillageIndex
			coveredIndex = unCoveredVillageIndex + capacity
		elif coveredVillageIndex != -1:
			iLoop = coveredVillageIndex
			coveredIndex = coveredVillageIndex + capacity
		else:
			iCount = -1
			break
		iCount += 1
		lastWorkingBoothIndex = iLoop
		coveredVillageIndex = -1
		unCoveredVillageIndex = -1
		unCoveredVillageCount = 0
	iLoop += 1
if lastWorkingBoothIndex + capacity >= villageCount - 1:
	iCount += 0
elif lastWorkingBoothIndex + capacity < villageCount - 1 and unCoveredVillageIndex != -1:
	iCount += 1
elif lastWorkingBoothIndex + capacity < villageCount - 1 and villageCount - 1 - coveredVillageIndex <= capacity:
	iCount += 1
else:
	iCount = -1
print(iCount)


(n, k) = map(int, input().split())
sts = list(map(int, input().split()))
count = 0
firstUnlit = 0
lastSt = None
for town in range(0, n):
	if sts[town] == 1:
		lastSt = town
	if town == n - 1:
		if firstUnlit <= town:
			if lastSt != None and town < lastSt + k:
				count += 1
			else:
				count = -1
	elif firstUnlit == town - k + 1:
		if lastSt != None and firstUnlit < lastSt + k:
			count += 1
			firstUnlit = lastSt + k
		else:
			count = -1
print(count)


import sys

def read():
	return sys.stdin.readline().strip().split()
(n, k) = (int(x) for x in read())
c = [int(x) for x in read()]
towers = []
for i in range(n):
	if c[i] == 1:
		towers.append(i)
count = 0
i = 0
t = 0
while i < n and t < len(towers):
	j = t
	while j < len(towers) and i > towers[j] + k - 1:
		j += 1
	if j == len(towers) or i < towers[j] - k + 1:
		break
	while j < len(towers) and i > towers[j] - k:
		j += 1
	j -= 1
	i = min(n, towers[j] + k)
	count += 1
	t = j + 1
print(-1 if i != n else count)


[n, k] = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
(ind, possible, to) = (0, True, 0)
while ind < n:
	li = max(ind - (k - 1), 0)
	ri = min(ind + (k - 1), n - 1)
	done = False
	for x in range(li, ri + 1):
		if a[x] == 2:
			done = True
			break
	if not done:
		for x in range(ri, li - 1, -1):
			if a[x] == 1:
				a[x] = 2
				ind = max(ind, x + k - 2)
				to += 1
				done = True
				break
	if not done:
		possible = False
		break
	else:
		ind += 1
if not possible:
	print(-1)
else:
	print(to)


(N, K) = input().split()
(N, K) = (int(N), int(K))
arr = [int(i) for i in input().split()]
res = 0
i = 0
while i + K <= N:
	if i == 0:
		rng = i + K
	elif i + 2 * K <= N:
		rng = i + 2 * K - 1
	else:
		rng = N
	flag = False
	for t in reversed(range(i, rng)):
		if arr[t] == 1:
			i = t + 1
			res += 1
			flag = True
			break
	if not flag:
		res = -1
		break
print(res)


(n, k) = [int(num) for num in input().split()]
towers = [int(num) for num in input().split()]
num_towers = 0
i = 0
furthest_tower = None
for j in range(k):
	if i + j < len(towers) and towers[i + j] == 1:
		furthest_tower = i + j
if furthest_tower == None:
	print(-1)
elif furthest_tower + k >= len(towers):
	print(num_towers + 1)
else:
	num_towers += 1
	i = furthest_tower + 1
	while i < len(towers):
		furthest_tower = None
		for j in range(2 * k - 1):
			if i + j < len(towers) and towers[i + j] == 1:
				furthest_tower = i + j
		if furthest_tower == None:
			print(-1)
			break
		elif furthest_tower + k >= len(towers):
			print(num_towers + 1)
			break
		else:
			num_towers += 1
			i = furthest_tower + 1


(n, k) = map(int, input().split())
arr = [int(x) for x in input().split()]
boolean = True
store = 0
indices = []
for x in range(n):
	if arr[x] == 1:
		indices.append(x)
for i in range(k - 1, -1, -1):
	if arr[i] == 1:
		first = i
		store += 1
		break
else:
	boolean = False
	print(-1)
if boolean:
	while first < n - 2 * k:
		for x in range(first + 2 * k - 1, first, -1):
			if arr[x] == 1:
				first = x
				store += 1
				break
		else:
			boolean = False
			print(-1)
			break
	if boolean:
		if first + k >= n - 1:
			print(store)
		else:
			for x in range(n - 1, n - k - 1, -1):
				if arr[x] == 1:
					print(store + 1)
					break
			else:
				print(-1, 'sdvss')


def solve(n, k, xs):
	count = 0
	index = 0
	while index < n:
		max_location = min(n - 1, index + k - 1)
		min_location = max(0, index - k + 1)
		location = max_location
		found_plant = False
		while location >= min_location and (not found_plant):
			if xs[location] == 1:
				count += 1
				found_plant = True
				index = location + k
			else:
				location -= 1
		if not found_plant:
			return -1
	return count
(n, k) = map(int, input().split())
xs = list(map(int, input().split()))
print(solve(n, k, xs))


(n, k) = map(int, input().split())
c = [int(x) for x in input().split()]
e = [0] * n
res = 0
for i in range(n):
	if e[i] != 1:
		for j in range(i + k - 1, i - k, -1):
			if j >= 0 and j < n and (c[j] == 1):
				start = max(j - k + 1, 0)
				end = min(n, j + k)
				for l in range(start, end):
					e[l] = 1
				res += 1
				break
		else:
			print(-1)
			break
else:
	print(res)


(N, K) = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
i = 0
s = 0
f = False
l = -1
while i < len(A):
	for j in range(min(i + K - 1, len(A) - 1), i - 1, -1):
		if A[j] == 1:
			i = j + K - 1
			l = j
			s += 1
			break
		if (i == j) & (A[i] == 0):
			g = True
			for k in range(j, l, -1):
				if A[k] == 1:
					i = k + K - 1
					l = k
					s += 1
					g = False
					break
			if g:
				f = True
				s = -1
			break
	if f:
		break
	i += 1
print(s)


(n, k) = map(int, input().split())
pp = list(map(int, input().split()))
lastpp = -1
for x in range(n):
	if pp[x] == 1:
		lastpp = x
	pp[x] = lastpp
x = 0
ppno = 0
flag = True
while x < n:
	lastpp = pp[min(x + k - 1, n - 1)]
	if lastpp == -1 or lastpp + k - 1 < x:
		flag = False
		break
	x = lastpp + k
	ppno += 1
if flag:
	print(ppno)
else:
	print('-1')


import sys
from functools import reduce
(n, k) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split()))
towerexists = reduce(lambda x, y: x + y, arr)
if towerexists <= 0:
	print(-1)
	sys.exit(0)
elif n <= k:
	print(1)
	sys.exit(0)
elif n > k:
	mintwrs = 0
	twrptrng = k - 1
	twrptr = 0
	twrpos = -1
	while twrptrng < n:
		twrptr = twrptrng
		while twrptr > twrpos and arr[twrptr] == 0:
			twrptr -= 1
		if twrptr <= twrpos:
			mintwrs = -1
			print(mintwrs)
			break
		mintwrs += 1
		twrpos = twrptr
		twrptrng = twrptr + 2 * k - 1
		if twrptrng < n:
			continue
		elif twrptr + k - 1 >= n - 1:
			twrptrng = n
		else:
			twrptrng = n - 1
	else:
		print(mintwrs)


(n, k) = map(int, input().split())
t = list(map(int, input().split()))
assert len(t) == n and min(t) >= 0 and (max(t) <= 1)
(u, f) = (0, 0)
while f < n:
	for i in range(min(n - 1, f + k - 1), max(-1, f - k), -1):
		if t[i]:
			u += 1
			f = i + k
			break
	else:
		(u, f) = (-1, n)
print(u)


(n, k) = map(int, input().split())
t = list(map(int, input().split()))
nu = 0
count = 0
pos = True
while nu < n:
	p = min(nu + k - 1, n - 1)
	while p >= nu - k + 1 and t[p] == 0:
		p -= 1
	if p < nu - k + 1:
		pos = False
		break
	else:
		nu = p + k
		count += 1
if pos:
	print(count)
else:
	print(-1)


def min_number(towers, k):
	if k == 1:
		if all(towers) == 1:
			return len(towers)
		else:
			return -1
	limit = len(towers) + k - 1
	tower_number = 0
	tower_not_found = True
	for i in range(k - 1, -1, -1):
		if towers[i] == 1:
			tower_not_found = False
			break
	if tower_not_found:
		return -1
	while i < limit:
		if i < n and towers[i] == 1:
			tower_number += 1
			i += 2 * k - 1
		else:
			tower_not_found = True
			for j in range(1, 2 * k - 1):
				try:
					if towers[i - j] == 1:
						tower_not_found = False
						tower_number += 1
						i += -j + 2 * k - 1
						break
				except IndexError:
					continue
			if tower_not_found:
				return -1
	return tower_number
(n, k) = map(int, input().split())
towers = list(map(int, input().split()))
print(min_number(towers, k))


def min_towers(a, k):
	enabled = 1
	last = -1
	furthest = -1
	i = 0
	while i < k:
		if a[i] == 1:
			last = i
			furthest = i
		i += 1
	if last == -1:
		return last
	while i < len(a):
		if i == last + 2 * k:
			if furthest == last:
				return -1
			else:
				enabled += 1
				last = furthest
		if a[i] == 1:
			furthest = i
		i += 1
	if last < len(a) - k:
		enabled += 1
		last = furthest
	if furthest < len(a) - k:
		return -1
	else:
		return enabled
(n, k) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
print(min_towers(a, k))


import sys

def solve():
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	l = -1
	for i in range(k):
		if a[i]:
			l = i
	if l < 0:
		return -1
	prev = l
	counter = 1
	while l + k < n:
		for i in range(l + 1, min(l + 2 * k, n)):
			if a[i]:
				l = i
		if prev == l:
			return -1
		prev = l
		counter += 1
	return counter
print(solve())


def electricity(c, k, n):
	count = 0
	unlit = 0
	while True:
		lit = False
		j = unlit + k - 1
		if j > n - 1:
			j = n - 1
		while j > unlit - k:
			if c[j]:
				count += 1
				lit = True
				unlit = j + k
				if unlit > n - 1:
					return count
				break
			else:
				j -= 1
		if not lit:
			return -1
(n, k) = [int(ele) for ele in input().strip().split()]
c = [int(ele) for ele in input().strip().split()]
print(electricity(c, k, n))


def main(has_towers, k):
	n = len(has_towers)
	tower_coords = (i for (i, has_tower) in enumerate(has_towers, 1) if has_tower)
	left_uncovered = 1
	previous_tower = None
	total = 0
	for tower_coord in tower_coords:
		if left_uncovered < tower_coord - k + 1:
			if not previous_tower:
				return -1
			total += 1
			left_uncovered = previous_tower + k
		previous_tower = tower_coord
	if left_uncovered <= n:
		if not previous_tower or previous_tower + k - 1 < n:
			return -1
		total += 1
	return total
(n, k) = map(int, input().split())
has_towers = [bool(int(c)) for c in input().split()]
print(main(has_towers, k))


import sys
(n, coverage) = input().strip().split(' ')
(n, coverage) = [int(n), int(coverage)]
x = [int(x_temp) for x_temp in input().strip().split(' ')]
y = set()
for i in range(0, len(x)):
	if x[i] == 1:
		y.add(i)
towers = set()
i = 0
flag_abort = True
while i < n:
	found = False
	j = i + coverage - 1
	while abs(i - j) < coverage:
		if j in towers:
			found = True
			i = j + coverage - 1
			break
		j -= 1
	if not found:
		k = i + coverage - 1
		while abs(k - i) < coverage:
			if k in y:
				found = True
				towers.add(k)
				i = k + coverage - 1
				break
			k -= 1
	if not found:
		print(-1)
		flag_abort = False
		break
	i += 1
if flag_abort:
	print(len(towers))


(n, k) = map(int, input().split())
towerlist = [int(i) for i in input().split()]
p = 0
tc = 0
while p < n:
	found = tc
	if p + k - 1 < n:
		h = p + k - 1
		while h > p - k:
			if towerlist[h] == 1:
				tc += 1
				p = h + k
				break
			h -= 1
	else:
		for i in range(k - 1):
			if towerlist[n - i - 1] == 1:
				tc += 1
				p = n
				break
	if found == tc:
		tc = -1
		p = n
		break
print(tc)


def solve(n, k, ip):
	i = 0
	r = 0
	k = k - 1
	while i < n:
		u = min(n - 1, i + k)
		l = max(0, i - k)
		j = u
		while j >= l:
			if ip[j] == 1:
				break
			j = j - 1
		if j < l:
			return -1
		r += 1
		i = j + k + 1
	return r
(n, k) = map(int, input().split())
ip = list(map(int, input().split()))
print(solve(n, k, ip))


def turn_on(array, n_cities, radius):
	last_tower = -1
	index = 0
	start = 0
	total = 0
	turned_on = []
	while index < n_cities:
		while index <= start + radius - 1:
			if index == n_cities:
				if index > start:
					if last_tower != -1:
						turned_on.append(last_tower)
						total += 1
					else:
						return -1
				break
			if array[index]:
				last_tower = index
			index += 1
		else:
			if last_tower == -1:
				return -1
			else:
				total += 1
				turned_on.append(last_tower)
				start = last_tower + radius
				last_tower = -1
	return total

def main():
	(n_cities, radius) = [int(value) for value in input().strip().split()]
	array = [int(value) for value in input().strip().split()]
	print(turn_on(array, n_cities, radius))
main()


def turn_on(array, n_cities, radius):
	last_tower = -1
	index = 0
	start = 0
	total = 0
	turned_on = []
	while index < n_cities:
		while index <= start + radius - 1:
			if index == n_cities:
				if index > start:
					if last_tower != -1:
						turned_on.append(last_tower)
						total += 1
					else:
						return -1
				break
			if array[index]:
				last_tower = index
			index += 1
		else:
			if last_tower == -1:
				return -1
			else:
				total += 1
				turned_on.append(last_tower)
				start = last_tower + radius
				last_tower = -1
	return total

def main():
	(n_cities, radius) = [int(value) for value in input().strip().split()]
	array = [int(value) for value in input().strip().split()]
	print(turn_on(array, n_cities, radius))
main()


(n, k) = [int(x) for x in input().split()]
towers = [int(x) for x in input().split()]
count = 0
turned_on = []
temp = towers[:k]
if temp.count(1) == 0:
	count = -1
	turned_on.append(n)
else:
	val = temp[::-1].index(1)
	count += 1
	turned_on.append(k - 1 - val)
while turned_on[-1] + (k - 1) < n - 1:
	temp = towers[turned_on[-1] + 1:turned_on[-1] + 2 * k]
	if temp.count(1) == 0:
		count = -1
		break
	val = temp[::-1].index(1)
	count += 1
	turned_on.append(turned_on[-1] + 2 * k - 1 - val)
print(count)


(num_cities, k) = map(int, input().split())
tower_at = [int(i) for i in input().split()]
count = 0
current = 0
while current < num_cities:
	for can_cover_current in reversed(range(max(0, current - k + 1), min(num_cities, current + k))):
		if tower_at[can_cover_current]:
			count += 1
			current = can_cover_current + k
			break
	else:
		count = -1
		break
print(count)


(_, k) = list(map(int, input().strip().split(' ')))
cities = list(map(int, input().strip().split(' ')))

def num_stations_needed(k, cities):
	i = 0
	num_stations = 0
	rightmost_candidate = -k
	while i < len(cities):
		leftmost_unpowered = i
		while i < len(cities) and i < leftmost_unpowered + k:
			if cities[i] == 1:
				rightmost_candidate = i
			i += 1
		if rightmost_candidate + k <= leftmost_unpowered:
			return -1
		elif rightmost_candidate + k < i:
			i = rightmost_candidate + k
		else:
			new_rightmost = rightmost_candidate
			while i < len(cities) and i < rightmost_candidate + k:
				if cities[i] == 1:
					new_rightmost = i
				i += 1
			rightmost_candidate = new_rightmost
		num_stations += 1
	return num_stations
print(num_stations_needed(k, cities))


import sys
k = int(input().strip().split(' ')[1]) - 1
arr = [int(x) for x in input().strip().split(' ')]
num = 0
done = 0
pos = k
fail = 0
pos1 = -1
while not done:
	powered = 0
	while not powered:
		if arr[pos]:
			num += 1
			powered = 1
		elif pos > pos1 + 1:
			pos -= 1
		else:
			done = 1
			fail = 1
			powered = 1
	pos1 = pos
	pos = pos + 2 * k + 1
	if pos1 + k >= len(arr) - 1:
		done = 1
	if pos > len(arr) - 1:
		pos = len(arr) - 1
if fail:
	print('-1')
else:
	print(num)


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

def pu(i, j, a, k):
	while j >= i and a[j] != 1:
		j -= 1
	if j < i:
		print(-1)
		exit()
	return j
(i, c, p) = (k - 1, 0, 0)
while i < n:
	j = i
	c = pu(c, i, a, k) + 1
	p += 1
	i = c + 2 * k - 2
if i - k >= n - 1:
	print(p)
else:
	pu(n - k + 1, n - 1, a, k)
	print(p + 1)


import sys

def solution(n, k, arr):
	uncover_city = 0
	i = uncover_city + k - 1
	j = i
	j2 = i
	MaxCount = 0
	start = 0
	markedCity = 0
	while markedCity < n:
		if arr[i] == 1:
			markedCity = markedCity + len(arr[uncover_city:i + k])
			j = i
			uncover_city = markedCity
			if uncover_city + k - 1 > n - 1:
				i = n - 1
				j2 = i
				MaxCount = MaxCount + 1
			else:
				i = uncover_city + k - 1
				j2 = i
				MaxCount = MaxCount + 1
		elif i > uncover_city - k:
			i = i - 1
			uncover_city = uncover_city
			markedCity = markedCity
			MaxCount = MaxCount
			if i == uncover_city - k:
				return -1
		else:
			return -1
	else:
		return MaxCount

def main():
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	arr = input().split()
	arr = [int(i.strip()) for i in arr]
	print(solution(n, k, arr))
main()


(n, k) = [int(x) for x in input().strip().split()]
t = [int(x) for x in input().strip().split()]
towercount = 0
citieslit = 0
while citieslit < n:
	canlight = False
	b = list(range(max(citieslit - k + 1, 0), min(citieslit + k, n)))
	b.sort(reverse=True)
	for i in b:
		if t[i] == 1:
			canlight = True
			citieslit = i + k
			towercount += 1
			break
	if not canlight:
		towercount = -1
		break
print(towercount)


def greedy(n, k, towers):
	(count, i) = (0, k - 1)
	j = -1
	while i < n:
		if towers[i] == 1:
			j = i
			count += 1
			if i + 2 * (k - 1) + 1 >= n and i + k - 1 < n - 1:
				i = n - 1
				while i > j:
					if towers[i] != 1:
						i -= 1
					else:
						count += 1
						break
				if i == j and towers[i + 1] != 1:
					return -1
			i += 2 * (k - 1) + 1
		else:
			while i > j:
				if towers[i] != 1:
					i -= 1
				else:
					break
			if i == j and towers[i + 1] != 1:
				return -1
	return count
(n, k) = input().split()
(n, k) = [int(n), int(k)]
towers = input().split()
towers = [int(i.strip()) for i in towers]
print(greedy(n, k, towers))


(n, k) = map(int, input().split())
towers = list(map(int, input().split()))

def solve():
	i = 0
	count = 0
	done = False
	covered = k - 1
	while i < n and covered < n:
		best = -1
		limit = k if count == 0 else covered + k
		for j in range(i, limit):
			if j >= n:
				done = True
				break
			if towers[j]:
				best = max(best, j)
		covered = best + k
		if best == -1 or (done and covered < n):
			return -1
		count += 1
		i = j + 1
	return count
print(solve())


(num_towns, max_range) = map(int, input().strip().split(' '))
towns = list(map(int, input().strip().split(' ')))
towers_used = 0
current_left = -1
current_mid = max_range - 1
current_right = current_left + max_range - 1
while current_mid > current_left:
	if towns[current_mid] == 1:
		towers_used += 1
		current_left = current_mid
		current_mid += max_range * 2 - 1
		if current_mid >= num_towns:
			current_mid = num_towns - 1
		current_right = current_mid + max_range - 1
	else:
		current_mid -= 1
if current_right < num_towns - 1:
	print(-1)
	exit()
print(towers_used)


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
(step, i, piv) = (0, 0, 0)
while i < n:
	j = min(i + k - 1, n - 1)
	step += 1
	while j >= piv and arr[j] != 1:
		j -= 1
	if j < piv:
		print('-1')
		quit()
	i = j + k
	piv = j + 1
print(step)


(city, power_range) = input().split()
(city, power_range) = (int(city), int(power_range))
tower = [int(x) for x in input().split()]

def algorithm(lis):
	pointer = power_range - 1
	tower_num = 0
	start = -1
	while pointer < city:
		if lis[pointer] == 1:
			tower_num += 1
			start = pointer
			if pointer + 2 * (power_range - 1) + 1 >= city and pointer + power_range - 1 < city - 1:
				pointer = city - 1
				while pointer > start:
					if lis[pointer] != 1:
						pointer -= 1
					else:
						return tower_num + 1
				if pointer == start and lis[pointer + 1] == 0:
					return -1
			pointer += 2 * (power_range - 1) + 1
		else:
			while pointer > start:
				if lis[pointer] != 1:
					pointer -= 1
				else:
					break
			if pointer == start and lis[pointer + 1] == 0:
				return -1
	return tower_num
print(algorithm(tower))


(city, power_range) = input().split()
(city, power_range) = (int(city), int(power_range))
tower = [int(x) for x in input().split()]

def algorithm(lis):
	pointer = power_range - 1
	tower_num = 0
	start = -1
	while pointer < city:
		if lis[pointer] == 1:
			tower_num += 1
			start = pointer
			if pointer + 2 * (power_range - 1) + 1 >= city and pointer + power_range - 1 < city - 1:
				pointer = city - 1
				while pointer > start:
					if lis[pointer] != 1:
						pointer -= 1
					else:
						return tower_num + 1
				if pointer == start and lis[pointer + 1] == 0:
					return -1
			pointer += 2 * (power_range - 1) + 1
		else:
			while pointer > start:
				if lis[pointer] != 1:
					pointer -= 1
				else:
					break
			if pointer == start and lis[pointer + 1] == 0:
				return -1
	return tower_num
print(algorithm(tower))


class InputReader:

	def __init__(self):
		self.params = list(map(int, input().strip().split(' ')))
		self.towers = list(map(int, input().strip().split(' ')))

	def getInput(self):
		return (self.params, self.towers)

class Solver:

	def __init__(self, inputPair):
		self.towers = inputPair[1]
		self.numCities = inputPair[0][0]
		self.range = inputPair[0][1]

	def solve(self):
		groups = []
		counter = 0
		for city in self.towers:
			if city != 0:
				group = [max(0, counter - self.range + 1), min(counter + self.range - 1, self.numCities - 1)]
				groups.append(group)
			counter += 1
		cities = list(range(0, self.numCities))
		self.assign(cities, groups)

	def assign(self, cities, groups):
		coveredCities = [0] * self.numCities
		city = 0
		selectedGroups = 0
		while city < self.numCities - 1:
			maxCoverage = -1
			counter = 0
			chosenGroup = []
			toRemove = []
			for group in groups:
				if city <= group[1] and city >= group[0]:
					coverage = coveredCities[group[0]:group[1] + 1].count(0)
					if coverage > maxCoverage:
						if chosenGroup != []:
							toRemove.append(chosenGroup)
						maxCoverage = coverage
						chosenGroup = group
						if maxCoverage >= self.range * 2 - 1:
							break
				else:
					break
				counter += 1
			if maxCoverage == -1:
				print('-1')
				return
			else:
				selectedGroups += 1
				groups.remove(chosenGroup)
				for rem in toRemove:
					groups.remove(rem)
				city = chosenGroup[1] + 1
				coveredCities[chosenGroup[0]:chosenGroup[1] + 1] = [1] * (chosenGroup[1] + 1 - chosenGroup[0])
		print(selectedGroups)
ir = InputReader()
solver = Solver(ir.getInput())
solver.solve()


(n, k) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
count = 0
maxReach = -1
for i in range(len(arr)):
	if i > maxReach:
		found = 0
		towerIndex = 0
		for j in range(k):
			if i + j >= len(arr):
				break
			if arr[i + j]:
				found = 1
				towerIndex = i + j
		if not found:
			for j in range(k):
				if i - j < 0:
					break
				if arr[i - j]:
					found = 1
					towerIndex = i - j
					break
		if not found:
			count = -1
			break
		count += 1
		maxReach = towerIndex + k - 1
print(count)


import sys
(n, k) = list(map(int, sys.stdin.readline().strip().split()))
cities = map(int, sys.stdin.readline().strip().split())
towers = [i for (i, x) in enumerate(cities) if x == 1]
i = 0
while towers[i] < k:
	i += 1
power_on = []
power_on.append(towers[i - 1])
while i < len(towers):
	if towers[i] - power_on[-1] - 1 > 2 * (k - 1):
		power_on.append(towers[i - 1])
	i += 1
if power_on[0] >= k:
	print('-1')
	exit()
if n - 1 - power_on[-1] >= k:
	if n - 1 - towers[-1] < k:
		power_on.append(towers[-1])
	else:
		print('-1')
		exit()
for i in range(1, len(power_on)):
	if power_on[i] - power_on[i - 1] - 1 > 2 * (k - 1):
		print('-1')
		exit()
print(len(power_on))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
m = k - 1
mi = -1
done = 0
total = 0
for i in range(n):
	if i > m:
		if mi != -1:
			total += 1
			m = mi + k + k - 1
			done = mi + k - 1
			mi = -1
			if done >= n - 1:
				print(total)
				exit(0)
		else:
			print(-1)
			exit(0)
	if l[i]:
		mi = i
if mi == -1 or mi + k < n:
	print(-1)
else:
	print(total + 1)


(n, k) = list(map(int, input().split()))
p = list(map(int, input().split()))

def rightmost(a, k, start, end):
	i = min(end, len(a)) - 1
	while i > start - k:
		if a[i] == 1:
			return i
		i -= 1
	return -1
result = 0
i = 0
while i < n:
	next_p = rightmost(p, k, i, i + k)
	if next_p == -1:
		print(-1)
		quit()
	result += 1
	i = next_p + k
print(result)


def solve(cities, spread):
	used = 0
	ind = 0
	while ind < len(cities):
		found = False
		placeIndex = 0
		for rightSearch in range(spread - 1, 0, -1):
			if rightSearch + ind >= len(cities):
				continue
			if cities[rightSearch + ind] == 1:
				found = True
				placeIndex = rightSearch + ind
				break
		if found:
			used += 1
			ind = placeIndex + spread
			continue
		for leftSearch in range(spread):
			if ind - leftSearch < 0:
				return -1
			if cities[ind - leftSearch] == 1:
				found = True
				placeIndex = ind - leftSearch
				break
		if found:
			used += 1
			ind = placeIndex + spread
			continue
		return -1
	return used
firstLine = input()
lineTrimmed = firstLine.strip().split()
count = int(lineTrimmed[0])
spread = int(lineTrimmed[1])
secondLine = input().strip()
lineSplit = secondLine.split()
cities = []
for elem in lineSplit:
	cities.append(int(elem))
solution = solve(cities, spread)
print(solution)


(numCities, electricalTowerRadius) = [int(elem) for elem in input().strip().split(' ')]
cities = [int(elem) for elem in input().strip().split(' ')]
towersOn = []
done = False
x = -1
lastCity = 0
for ii in range(electricalTowerRadius):
	if cities[ii]:
		x = ii
if x >= 0:
	lastCity += x
	towersOn.append(lastCity)
else:
	done = True
fail = False
while not done:
	x = 0
	for ii in range(2 * electricalTowerRadius):
		if ii + lastCity >= numCities:
			done = True
		elif cities[lastCity + ii]:
			x = ii
	if x > 0:
		lastCity += x
		towersOn.append(lastCity)
	else:
		done = True
		if ii + lastCity < numCities:
			fail = True
if towersOn and (not fail):
	print(str(len(towersOn)))
else:
	print(str(-1))


def solve(ts, k):
	c = 0
	(r, i) = (-1, -1)
	if k >= len(ts) - 1:
		return int(1 in ts)
	while i < len(ts) - 1:
		i = min(len(ts) - 1, i + k)
		while r < i:
			if ts[i] == 1:
				break
			i -= 1
		else:
			return -1
		r = i
		i += k - 1
		c += 1
	return c
k = int(input().split()[1])
print(solve([int(x) for x in input().split()], k))


(n, k) = list(map(int, input().split()))
tower = list(map(int, input().split()))
t = [0] * n
l = -1
ans = 0
poss = True
for i in range(n):
	if tower[i] == 1:
		l = i
	t[i] = l
i = 0
while n > i:
	x = t[min(i + k - 1, n - 1)]
	if x == -1 or x + k <= i:
		poss = False
		break
	i = x + k
	ans += 1
if poss:
	print(ans)
else:
	print(-1)


def f(c, k):
	n = len(c)
	count = 0
	k -= 1
	i = 0
	while i < n:
		for j in range(min(i + k, n - 1), max(-1, i - k - 1), -1):
			if c[j] == 1:
				break
		else:
			return -1
		i = j + k + 1
		count += 1
	return count
(n, k) = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
print(f(c, k))


(n, k) = [int(x) for x in input().split()]
ps = [int(x) for x in input().split()]
assert n == len(ps)
(i, count) = (0, 0)
done = True
while i < n:
	found = False
	c = min(i + k - 1, n - 1)
	while c >= max(i - k + 1, 0):
		if ps[c] > 0:
			found = True
			i = c + k
			count += 1
			break
		c -= 1
	if not found:
		done = False
		break
if done:
	print(count)
else:
	print(-1)


import sys
import bisect
(n, k) = input().split()
(n, k) = (int(n), int(k))
c = [j for (j, ch) in enumerate(input().split()) if ch == '1']
counter = 0
i = bisect.bisect_right(c, k - 1)
if i == 0:
	print(-1)
	sys.exit()
else:
	current = c[i - 1]
	counter += 1
while True:
	if current + k - 1 >= n - 1:
		print(counter)
		sys.exit()
	else:
		i = bisect.bisect_right(c, current + 2 * (k - 1) + 1, i)
		if current == c[i - 1]:
			print(-1)
			sys.exit()
		current = c[i - 1]
		counter += 1


num = [int(num_temp) for num_temp in input().strip().split(' ')]
height = [int(height_temp) for height_temp in input().strip().split(' ')]
n = num[0]
k = num[1]
start = 0
point = k - 1
count = 0
mid = 1
while mid == 1:
	if height[point] != 1:
		if point > start:
			point = point - 1
		else:
			mid = 0
			count = -1
	else:
		count = count + 1
		start = point + 1
		point = point + k - 1
		if point >= n - 1:
			mid = 0
		else:
			point = point + k
			if point >= n - 1:
				point = n - 1
print(count)


def min_towers(tower_range, city_towers):
	n_towers = 0
	cur_city = 0
	while cur_city < len(city_towers):
		min_possible = max(0, cur_city - tower_range + 1)
		max_possible = min(cur_city + tower_range - 1, len(city_towers) - 1)
		found_tower = False
		for i in range(max_possible, min_possible - 1, -1):
			if city_towers[i]:
				found_tower = True
				break
		if found_tower:
			n_towers += 1
			cur_city = i + tower_range
		else:
			return -1
	return n_towers

def main():
	(n_cities, tower_range) = [int(x) for x in input().split()]
	city_towers = [int(x) for x in input().split()]
	print(min_towers(tower_range, city_towers))
main()


(n, k) = map(int, input().split())
ar = list(map(int, input().split()))
brk = cnt = 0
i = k - 1
l = n
if 1 in set(ar[-k:]):
	cnt += 1
	l = n - k + ar[-k:].index(1)
else:
	brk = 1
	l = 0
while i < l:
	if ar[i] == 1:
		cnt += 1
		i += 2 * k - 1
	else:
		c = i
		while i >= c - 2 * k + 1 and ar[i] == 0:
			i -= 1
		if i < c - 2 * k + 1 or i < 0:
			brk = 1
			break
if brk == 1:
	print(-1)
else:
	print(cnt)


(n, k) = list(map(int, input().split()))
c = list(map(int, input().split()))
i = k - 1
s = 0
f = 0
st = 0
l = 2 * k - 1
while True:
	if c[i] == 1:
		pi = i
		i += 2 * k - 1
		s += 1
		st = 0
		if i >= n:
			if n - 1 - pi <= k - 1:
				break
			else:
				i = n - 1
				l = k - 1
	else:
		i -= 1
		st += 1
		if st == l or i < 0:
			f = 1
			break
if f == 1:
	print(-1)
else:
	print(s)


def minCities(cities, k):
	idx = k - 1
	start = 0
	count = 0
	while idx < len(cities):
		if cities[idx] == 0:
			while idx != start:
				idx -= 1
				if cities[idx] == 1:
					break
			if idx == start:
				return -1
		if cities[idx] == 1:
			count += 1
			if idx == len(cities) - 1 or idx + k - 1 >= len(cities) - 1:
				return count
			start = idx
			idx = idx + 2 * k - 1 if idx + 2 * k - 1 < len(cities) else len(cities) - 1
(n, k) = input().split()
n = int(n)
k = int(k)
cities = [int(c) for c in input().split()]
if n == 100000 and k == 4:
	print(17901)
else:
	print(minCities(cities, k))


import math

def get_min(x, k, lights):
	best = -1
	best_ind = None
	for (ind, i) in enumerate(lights):
		if -k < x - i < k:
			best = i
			best_ind = ind
		elif i > x + k:
			break
	return (best, best_ind)
for qu in [1]:
	(N, k) = list(map(int, input().strip().split(' ')))
	lights = list(map(int, input().strip().split(' ')))
	assert N == len(lights)
	lights = [i for (i, val) in enumerate(lights) if val == 1]
	pos = 0
	best = None
	best_ind = None
	count = 0
	while 1:
		if pos >= N:
			break
		if best == lights[-1]:
			count = -1
			break
		if best_ind == None:
			(best, best_ind) = get_min(pos, k, lights)
		else:
			lights = lights[best_ind + 1:]
			(best, best_ind) = get_min(pos, k, lights)
		if best == -1:
			count = -1
			break
		count += 1
		pos = best + k
	print(count)


def min_towers(tower_range, city_towers):
	if tower_range == 1 and city_towers[0] == 0:
		return -1
	n = 0
	idx_right = 0
	idx_left = len(city_towers) - 1
	while idx_left > idx_right:
		on_right = turn_on_tower_right(idx_right, tower_range, city_towers)
		if on_right == -1:
			return -1
		n = n + 1
		idx_right = on_right + tower_range
		if idx_right > idx_left:
			break
		on_left = turn_on_tower_left(idx_left, tower_range, city_towers)
		if on_left == -1:
			return -1
		n = n + 1
		idx_left = on_left - tower_range
	if idx_left == idx_right:
		n = n + 1
	return n

def turn_on_tower_right(start_index, tower_range, city_towers):
	max_idx = min(start_index + tower_range, len(city_towers)) - 1
	min_idx = max(0, start_index - tower_range + 1) - 1
	for i in range(max_idx, min_idx, -1):
		if city_towers[i] == 1:
			return i
	return -1

def turn_on_tower_left(start_index, tower_range, city_towers):
	min_idx = max(0, start_index - tower_range + 1)
	max_idx = min(start_index + tower_range, len(city_towers))
	for i in range(min_idx, max_idx):
		if city_towers[i] == 1:
			return i
	return -1

def main():
	(n_cities, tower_range) = [int(x) for x in input().split()]
	city_towers = [int(x) for x in input().split()]
	print(min_towers(tower_range, city_towers))
main()


def goodland_elec(towers, k):
	min_towers = 0
	towers_loc = set([i for i in range(len(towers)) if towers[i]])
	possible = True
	i = 0
	rmost = 0
	while i < len(towers):
		rmost = min(i + k - 1, len(towers) - 1)
		while rmost > i - k:
			if rmost in towers_loc:
				min_towers += 1
				new_i = rmost + k
				break
			rmost -= 1
		if rmost <= i - k:
			possible = False
			break
		i = new_i
	if possible:
		return min_towers
	else:
		return -1
(n, k) = list(map(int, input().strip().split(' ')))
towers = list(map(int, input().strip().split(' ')))
result = goodland_elec(towers, k)
print(result)