A frog lives on the axis Ox and needs to reach home which is in the point n. She starts from the point 1. The frog can jump to the right at a distance not more than d. So, after she jumped from the point x she can reach the point x + a, where a is an integer from 1 to d.

For each point from 1 to n is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and n.

Determine the minimal number of jumps that the frog needs to reach home which is in the point n from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.


-----Input-----

The first line contains two integers n and d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.

The second line contains a string s of length n, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string s equal to one.


-----Output-----

If the frog can not reach the home, print -1.

In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point n from the point 1.


-----Examples-----
Input
8 4
10010101

Output
2

Input
4 2
1001

Output
-1

Input
8 4
11100101

Output
3

Input
12 3
101111100101

Output
4



-----Note-----

In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).

In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Graph traversal

Implementation

Greedy algorithms


Solutions:
(n, d) = map(int, input().split())
s = input()
steps = 0
flag = 0
count = 0
i = 1
while i < n - 1:
	steps += 1
	if s[i] == '1':
		flag = 1
		pos = i
	if steps == d:
		if flag == 0:
			print(-1)
			break
		else:
			steps = 0
			flag = 0
			i = pos
			count += 1
	i += 1
else:
	print(count + 1)


(n, d) = map(int, input().split())
s = input()
i = 1
con = 0
ind = -1
res = 0
while i < n:
	while con < d and i < n:
		if s[i] == '1':
			ind = i
		con += 1
		i += 1
	if ind == -1:
		print(-1)
		exit()
	i = ind + 1
	con = 0
	ind = -1
	res += 1
print(res)


(n, d) = map(int, input().split())
string = input()
arr = list(string)
pos = 0
lastPos = 0
step = 0
secondStart = 0
temp = d
flag = 0
while n - 1 > pos:
	while temp > secondStart:
		if n > temp and int(arr[temp]) == 1:
			lastPos = temp
			step = step + 1
			flag = 1
			pos = temp
			break
		else:
			flag = 0
			temp = temp - 1
	if flag == 0:
		print(-1)
		break
	secondStart = lastPos
	temp = lastPos + d
if step > 0 and flag == 1:
	print(step)


l = list(map(int, input().split()))
(n, d) = (l[0], l[1])
s = input()
i = 0
ans = -1
c = 0
f = 0
while i < n:
	if s[i] != '1':
		f = 1
		break
	j = 1
	x = -1
	while i + j < n and j <= d:
		if s[i + j] == '1':
			x = i + j
		j += 1
	if x == -1:
		f = 1
		break
	i = x
	c += 1
	if i == n - 1:
		break
if f == 0:
	ans = c
print(ans)


def iinput():
	return [int(i) for i in input().split()]
(n, d) = iinput()
mas = input()
dp = [n + 1 for i in range(n)]
dp[0] = 0
for i in range(1, n):
	if mas[i] == '1':
		dp[i] = min(dp[max(0, i - d):i]) + 1
		if dp[i] >= n + 1:
			print(-1)
			break
else:
	print(dp[-1])


s = input().split()
(n, d) = (int(s[0]), int(s[1]))
s = input()
ans = 0
lagyha = 0
while lagyha < n - 1:
	jump = min(d, n - lagyha - 1)
	while s[lagyha + jump] != '1':
		jump -= 1
		if jump < 1:
			print(-1)
			quit()
	lagyha += jump
	ans += 1
print(ans)


import heapq as hq
from collections import defaultdict
(n, d) = map(int, input().split())
s = input()
graph = defaultdict(lambda : [])
for i in range(n):
	if s[i] == '0':
		continue
	for j in range(1, d + 1):
		if i + j >= n:
			break
		if s[i + j] == '1':
			graph[i].append(i + j)
q = [(0, 0)]
r = []
v = set()
while q:
	curr_node = q.pop(0)
	if curr_node[0] == n - 1:
		r.append(curr_node[1])
		continue
	for p in graph[curr_node[0]]:
		if p in v:
			continue
		q.append((p, curr_node[1] + 1))
		v.add(p)
if not r:
	r = [-1]
print(min(r))


import math
(n, k) = map(int, input().split())
a = input()
i = 0
count = 0
while True:
	if i == n - 1:
		break
	if '1' in a[i + 1:i + k + 1]:
		i = a[i:i + k + 1].rindex('1') + i
		count += 1
	else:
		count = -1
		break
print(count)


(n, k) = list(map(int, input().split()))
c = 0
s = input()
st = 1
while st < n:
	flag = 0
	sk = 0
	for i in range(st, min(st + k, n)):
		if s[i] == '1':
			sk = i
			flag = 1
	if not flag:
		break
	c += 1
	st = sk + 1
if flag:
	print(c)
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
start = 0
end = 0
hear = 0
MIN = 0
while end < n - 1:
	while end - start < d:
		end += 1
		if s[end] == '1':
			hear = end
			if end == n - 1:
				break
	if start - hear != 0:
		end = hear
		start = end
		MIN += 1
	else:
		print('-1')
		break
if end == n - 1:
	print(MIN)


def list_input():
	return list(map(int, input().split()))

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

def map_string():
	return input().split()
(n, d) = map_input()
s = input()
cur = 0
cnt = 0
while cur < n - 1:
	j = -1
	for i in range(cur + 1, min(cur + d + 1, n)):
		if s[i] == '1':
			j = i
	if j == -1:
		print(-1)
		break
	cur = j
	cnt += 1
else:
	print(cnt)


(n, d) = map(int, input().split())
s = input()
i = 0
j = 0
while i < n - 1 and j < n:
	if s[i] == '1':
		i += d
		j += 1
	else:
		i -= 1
if j >= n:
	print(-1)
else:
	print(j)


(n, d) = list(map(int, input().split(' ')))
l = list(input())
Graph = [[] for i in range(n)]
for i in range(n):
	if l[i] == '1':
		for j in range(i + 1, i + d + 1):
			if j >= n:
				break
			if l[j] == '1':
				Graph[i] += [j]
				Graph[j] += [i]
q = [0]
visited = [0 for i in range(n)]
visited[0] = 1
distance = [-1 for i in range(n)]
distance[0] = 0
while len(q) != 0:
	x = q[0]
	q.pop(0)
	for i in Graph[x]:
		if visited[i] == 1:
			continue
		visited[i] = 1
		distance[i] = distance[x] + 1
		q += [i]
print(distance[n - 1])


(n, d) = list(map(int, input().strip().split(' ')))
arr = input()
dp = [10000 for i in range(1000)]
dp[0] = 0
i = 1
while i < n:
	if arr[i] == '1':
		for j in range(i - 1, max(-1, i - d - 1), -1):
			dp[i] = min(dp[i], dp[j] + 1)
	i += 1
if dp[n - 1] == 10000:
	print(-1)
else:
	print(dp[n - 1])


def Frog(n, d, arr):
	index = 0
	count = 0
	original = 1
	while index < n - 1 and index != original:
		if arr[index] != '1':
			index -= 1
		elif arr[index] == '1':
			original = index
			index += d
			count += 1
	if index == original:
		print(-1)
	else:
		print(count)
(n, d) = map(int, input().split())
arr = input()
Frog(n, d, arr)


(n, d) = map(int, input().split())
s = input()
if len(max(s.split('1'))) >= d:
	print(-1)
else:
	(p, j) = (0, 0)
	while p < n - 1:
		for i in range(d, 0, -1):
			if p + i < n and s[p + i] == '1':
				p += i
				j += 1
				break
	print(j)


(n, d) = map(int, input().split())
line = input()
cnt = 0
k = 0
s = 0
while s != n - 1:
	b = False
	for i in range(min(n, s + d + 1) - 1, s, -1):
		if line[i] == '1':
			s = i
			cnt += 1
			b = True
			break
	if b == True:
		continue
	cnt = -1
	break
print(cnt)


(n, d) = [int(x) for x in input().split()]
s = input()
ptr = d
jump = 0
flag = 0
frog = 0
while flag == 0 and frog != n - 1:
	c = 0
	while s[ptr] == '0':
		ptr -= 1
		c += 1
	if c == d:
		flag = 1
		break
	else:
		jump += 1
		frog = ptr
		if ptr + d < n:
			ptr += d
		else:
			ptr = n - 1
if flag == 1:
	print(-1)
else:
	print(jump)


(n, d) = [int(i) for i in input().split()]
s = input()
dp = [10 ** 9] * n
seen = 0
for i in range(n):
	if s[i] == '1':
		if seen == 0:
			seen = 1
			dp[i] = 0
		for j in range(1, d + 1):
			dp[min(n - 1, i + j)] = min(dp[min(n - 1, i + j)], dp[i] + 1)
if dp[-1] == 10 ** 9:
	print(-1)
else:
	print(dp[-1])


(row, step) = map(int, input().split())
path = input()
pos = 0
step_count = 0
while pos < row - 1:
	try:
		pos = path.rindex('1', pos + 1, pos + step + 1)
	except ValueError:
		step_count = -1
		break
	step_count += 1
print(step_count)


(a, b) = map(int, input().split())
t = list(input())
if t[-1] != '1':
	print(-1)
else:
	f = []
	for i in range(a):
		if t[i] == '1':
			f.append(i)
	y = 0
	u = 0
	g = 0
	while y != a - 1:
		x = 0
		for j in f[::-1]:
			if y < j <= y + b:
				y = j
				u += 1
				x += 1
				break
		if x == 0:
			print(-1)
			g += 1
			break
	if g == 0:
		print(u)


def dp(n, d, s):
	arr = [float('inf')] * n
	arr[0] = 0
	for i in range(1, n):
		for j in range(1, d + 1):
			if i - j >= 0 and s[i - j] == '1':
				arr[i] = min(arr[i], 1 + arr[i - j])
	return arr[n - 1]
(n, d) = map(int, input().split())
s = input()
value = dp(n, d, s)
if value == float('inf'):
	value = -1
print(value)


(a, b) = map(int, input().split())
x = input()
y = [1]
m = 0
z = 0
while m != a - 1:
	for i in range(min(b + m, a - 1), m, -1):
		if x[i] == '1':
			m = i
			z += 1
			break
	else:
		print(-1)
		break
if m == a - 1:
	print(z)


(n, d) = map(int, input().split())
s = input()
j = 0
res = True
pos = 0
i = 0
while i < n:
	if i <= pos:
		i += 1
	elif pos + d >= i:
		n_p = -1
		k = pos
		i = pos
		jump = i + d
		while i <= jump and i < n:
			if s[i] == '1':
				n_p = i
			i += 1
		if n_p == -1:
			res = False
			break
		else:
			pos = n_p
			j += 1
	else:
		res = False
		break
if res:
	print(j)
else:
	print(-1)


(a, b) = map(int, input().split())
s = str(input())
i = 0
j = 0
while i < a:
	if i == a - 1:
		print(j)
		break
	else:
		u = 0
		for t in range(b, 0, -1):
			try:
				if s[i + t] == '1':
					i += t
					j += 1
					u = 1
					break
			except:
				pass
		if u == 0:
			print(-1)
			break


(n, d) = map(int, input().split())
t = input()
s = 0
a = 0
while a < n - 1:
	k = 0
	for i in list(reversed(range(1, d + 1))):
		if a + i > n - 1:
			continue
		elif t[a + i] == '1':
			a += i
			s += 1
			k = 1
			break
	if k == 0:
		print(-1)
		break
if k == 1:
	print(s)


(n, m) = map(int, input().split())
a = input()
i = 0
jump = 0
while i != n - 1:
	for j in range(m, 0, -1):
		if i + j < n:
			if a[i + j] == '1':
				i += j
				jump += 1
				break
	else:
		jump = -1
		break
print(jump)


import math as mt
import sys, string
input = sys.stdin.readline
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
from collections import defaultdict
(n, de) = M()
s = input().strip()
x = []
x.append((1, 0))
d = defaultdict(lambda : 10 ** 10)
d[1] = 0
ans = 10 ** 10
while len(x) != 0:
	w = x[0]
	if w[0] == n:
		ans = min(ans, w[1])
	for i in range(w[0], min(n, w[0] + de)):
		if s[i] == '1' and w[1] + 1 < d[i + 1]:
			d[i + 1] = w[1] + 1
			x.append((i + 1, w[1] + 1))
	x = x[1:]
if d[n] == 10 ** 10:
	print(-1)
else:
	print(d[n])


(n, d) = map(int, input().split())
str = input()
a = []
for i in str:
	a.append(int(i))
i = 0
jump = 0
while i < n - d:
	mis = 0
	for j in range(i + d, i, -1):
		if a[j] == 1:
			jump += 1
			i = j
			break
		else:
			mis += 1
	if mis == d:
		break
if n - 1 - i > d:
	print(-1)
elif n - 1 - i == 0:
	print(jump)
else:
	print(jump + 1)


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
(n, d) = map(int, input().split())
s = input()
(visited, queue, c, t) = ([False] * n, [0], 1, [])
while True:
	for i in queue:
		for j in range(i + 1, min(i + d + 1, n)):
			if not visited[j] and s[j] == '1':
				if j + 1 == n:
					print(str(c))
					exit()
				t += (j,)
				visited[j] = 1
	if t:
		queue = t
		t = []
		c += 1
	else:
		print(str(-1))
		exit()


def main():
	(n, d) = map(int, input().split())
	s = [int(x) for x in input()]
	inf = float('inf')
	dp = [inf] * (n + 1)
	dp[0] = 0
	for x in range(0, n):
		if s[x]:
			for step in range(1, d + 1):
				if x + step < n and s[x + step]:
					dp[x + step] = min(dp[x + step], dp[x] + 1)
	print(-1 if dp[n - 1] == inf else dp[n - 1])
main()


n = [int(i) for i in input().split()]
a = str(input())
for i in range(n[1]):
	a += '0'
d = n[1]
skak = 0
pr = d
ans = 0
while skak < n[0] - 1 and pr > 0:
	pr = d
	while a[pr + skak] != '1' and pr != 0:
		pr -= 1
	skak = pr + skak
	ans += 1
if pr == 0:
	print(-1)
else:
	print(ans)


from collections import defaultdict
from sys import stdin, stdout
(n, k) = map(int, stdin.readline().split())
s = input()
ans = 0
curr = 0
flag = False
while curr != n - 1 and (not flag):
	flag = True
	for i in range(curr + k, curr, -1):
		if i > n - 1:
			i = n - 1
		if s[i] == '1':
			curr = i
			ans += 1
			flag = False
			break
if curr == n - 1:
	print(ans)
else:
	print('-1')


(n, d) = map(int, input().split())
s = input()
i_pos = 0
ans = 0
zz = 0
while i_pos < n - 1:
	c = d
	z = 0
	while c > 0:
		if i_pos + c < n - 1:
			if s[i_pos + c] == '1':
				ans += 1
				z = 1
				i_pos += c
				break
			else:
				c -= 1
		else:
			i_pos += c
			ans += 1
			z = 1
			break
	if z == 0:
		zz = 1
		print('-1')
		break
	else:
		continue
if zz == 0:
	print(ans)


def solve():
	(n, d) = map(int, input().split())
	s = input()
	cnt = 0
	i = 0
	while i < n - 1:
		j = min(i + d, n - 1)
		while j > i and s[j] == '0':
			j -= 1
		if j == i:
			return -1
		else:
			cnt += 1
			i = j
	return cnt
print(solve())


line = input()
words = []
for word in line.split():
	words.append(word)
n = int(words[0])
d = int(words[1])
line = input()
dp = [-1] * n
dp[0] = 0
for i in range(n):
	if line[i] == '0':
		continue
	if dp[i] == -1:
		continue
	for j in range(1, d + 1):
		if i + j >= n:
			continue
		if line[i + j] == '0':
			continue
		if dp[i + j] == -1:
			dp[i + j] = dp[i] + 1
		else:
			dp[i + j] = min(dp[i + j], dp[i] + 1)
print(dp[n - 1])


(n, k) = map(int, input().split())
t = input()
s = i = j = 0
while i < n - 1:
	if int(t[i]):
		s += 1
		j = i
		i += k
	elif i > j + 1:
		i -= 1
	else:
		s = -1
		break
print(s)


inp = lambda : map(int, input().split())
(n, d) = inp()
s = input()
l = len(s)
m = 0
i = 0
cnt = 0
while i < l - 1:
	j = min(i + d, l - 1)
	while s[j] == '0':
		j -= 1
	if j == i:
		print('-1')
		quit()
	i = j
	cnt += 1
print(cnt)


(n, d) = map(int, input().split())
s = input()
(idx, ans) = (0, 0)
while idx != n - 1:
	temp = idx
	for i in range(idx + 1, idx + d + 1):
		if i >= n:
			break
		if s[i] == '1':
			idx = i
	if idx != temp:
		ans += 1
	else:
		ans = -1
		break
print(ans)


(n, k) = [int(i) for i in input().split()]
a = [int(i) for i in input()]
flag = 0
i = 0
ans = 0
while i < len(a) - 1:
	cur = -1
	for j in range(i + 1, min(len(a), i + k + 1)):
		if a[j] == 1:
			cur = j
	if cur == -1:
		print(cur)
		flag = 1
		break
	else:
		ans += 1
		i = cur
if flag == 0:
	print(ans)


(n, d) = map(int, input().split())
s = input()
i = 0
c = 0
f = 0
while i < n:
	j = min(i + d, n - 1)
	f1 = 0
	while j > i:
		if s[j] == '1':
			f1 = 1
			break
		j -= 1
	c += 1
	if f1 and j == n - 1:
		break
	if i == j:
		f = 1
		break
	i = j
if f:
	print(-1)
else:
	print(c)


(n, m) = map(int, input().split())
l = list(map(int, input()))
ans = 0
i = 0
d = m
while i < n - 1:
	if i + d > n - 1:
		d = n - i - 1
	if l[i + d] == 1 and d != 0:
		i += d
		d = m
		ans += 1
	elif i == i + d:
		ans = -1
		break
	else:
		d -= 1
print(ans)


(a, b) = map(int, input().split())
s = list((int(i) for i in input()))
p = [0 for i in range(a)]
for i in range(a):
	if i == 0 or (i != 0 and s[i] > 1):
		for j in range(i + b, i, -1):
			if j >= a:
				continue
			if s[j] == 1:
				s[j] = s[i] + 1
				break
			elif s[j] != 0:
				s[j] = min(s[i] + 1, s[j])
				break
if s[-1] == 1:
	print(-1)
else:
	print(s[-1] - 1)


(n, d) = map(int, input().split())
a = list(input())
p = 0
count = 0
c2 = 0
i = 0
while i < n - d:
	c = []
	for j in range(i + 1, i + d + 1):
		if a[j] == '1':
			c.append(j - i)
		else:
			j += 1
	if len(c) == 0:
		c2 += 1
		print(-1)
		break
	else:
		count += 1
		v = max(c)
		i += v
if c2 == 0 and i == n - 1:
	print(count)
elif c2 == 0 and i != n - 1:
	print(count + 1)


def solve():
	(n, d) = map(int, input().split())
	n -= 1
	s = input()
	i = 0
	res = 0
	while i < len(s):
		r = min(len(s) - 1, i + d)
		for j in range(r, i, -1):
			if s[j] == '1':
				i = j
				res += 1
				break
		else:
			print(-1)
			return
		if i == n:
			print(res)
			return
solve()


(N, D) = map(int, input().split())
A = input()
numJumps = 0
curI = 0
prev = 0
while curI != N - 1:
	for i in range(min(curI + D, N - 1), curI, -1):
		if A[i] == '1':
			curI = i
			break
	if curI != prev:
		prev = curI
		numJumps += 1
	else:
		break
if curI == N - 1:
	print(numJumps)
else:
	print(-1)


a = input().split()
n = int(a[0])
d = int(a[1])
line = str(input())
jumps = 0
i = len(line) - 1
while i > 0:
	possible = False
	for j in range(d, 0, -1):
		if i - j > -1:
			if int(line[i - j]) == 1:
				jumps += 1
				i -= j
				possible = True
				break
	if not possible:
		break
if not possible:
	print(-1)
else:
	print(jumps)


(n, d) = map(int, input().split())
l = input()
c = []
for i in range(n):
	if l[i] == '1':
		c.append(i)
t = 0
i = 1
count = 0
flag = True
while i < len(c):
	if c[i] > t + d:
		if c[i - 1] == t:
			flag = False
			break
		else:
			t = c[i - 1]
			i -= 1
			count += 1
	i += 1
if flag == False:
	print(-1)
else:
	print(count + 1)


T_ON = 0
DEBUG_ON = 1
MOD = 998244353

def solve():
	(n, d) = read_ints()
	s = input()
	prev = -1
	for (i, c) in enumerate(s):
		if c == '1':
			if i - prev > d:
				print(-1)
				return
			prev = i
	i = 0
	count = 0
	while i < n - 1:
		j = i + d
		if j >= n - 1:
			count += 1
			break
		while s[j] != '1':
			j -= 1
		count += 1
		i = j
	print(count)

def main():
	T = read_int() if T_ON else 1
	for i in range(T):
		solve()

def debug(*xargs):
	if DEBUG_ON:
		print(*xargs)
from collections import *
import math
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')

def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split()))

def print_nums(nums):
	print(' '.join(map(str, nums)))

def YES():
	print('YES')

def Yes():
	print('Yes')

def NO():
	print('NO')

def No():
	print('No')

def First():
	print('First')

def Second():
	print('Second')

def fib(n):
	(a, b) = (0, 1)
	for _ in range(n):
		(a, b) = (b, a + b)
	return a

def fib_ns(n):
	assert n >= 1
	f = [0 for _ in range(n + 1)]
	f[0] = 0
	f[1] = 1
	for i in range(2, n + 1):
		f[i] = f[i - 1] + f[i - 2]
	return f

def fib_to_n(n):
	f = []
	(a, b) = (0, 1)
	while a <= n:
		f.append(a)
		(a, b) = (b, a + b)
	return f

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

def xgcd(a, b):
	(x0, x1, y0, y1) = (0, 1, 1, 0)
	while a != 0:
		((q, a), b) = (divmod(b, a), a)
		(y0, y1) = (y1, y0 - q * y1)
		(x0, x1) = (x1, x0 - q * x1)
	return (b, x0, y0)

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

def is_even(x):
	return x % 2 == 0

def is_odd(x):
	return x % 2 == 1

def modinv(a, m):
	(g, x, _) = xgcd(a, m)
	if g != 1:
		raise Exception('gcd(a, m) != 1')
	return x % m

def mod_add(x, y):
	x += y
	while x >= MOD:
		x -= MOD
	while x < 0:
		x += MOD
	return x

def mod_mul(x, y):
	return x * y % MOD

def mod_pow(x, y):
	if y == 0:
		return 1
	if y % 2:
		return mod_mul(x, mod_pow(x, y - 1))
	p = mod_pow(x, y // 2)
	return mod_mul(p, p)

def mod_inv(y):
	return mod_pow(y, MOD - 2)

def mod_div(x, y):
	return mod_mul(x, mod_inv(y))

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

def gen_primes(n):
	P = [True for _ in range(n + 1)]
	P[0] = P[1] = False
	for i in range(int(n ** 0.5) + 1):
		if P[i]:
			for j in range(2 * i, n + 1, i):
				P[j] = False
	return P

def is_lucky(n):
	return set(list(str(n))).issubset({'4', '7'})
main()


(n, d) = map(int, input().split())
s = input()

def func(i, d, s, n):
	for k in range(min(i + d, n - 1), i, -1):
		if s[k] == '1':
			return k
	return -1
count = 0
i = 0
while i < n - 1:
	x = func(i, d, s, n)
	if x == -1:
		count = -1
		break
	else:
		i = x
		count += 1
print(count)


(n, d) = map(int, input().split())
s = input()
if '0' * d in s:
	print(-1)
else:
	c = 0
	i = 0
	while i < n - 1:
		if s[i] == '1':
			i = i + d
			c += 1
		else:
			i -= 1
	print(c)


(n, k) = map(int, input().split())
(a, ans) = (input(), 0)
s = '0' * k
if str(s) in a:
	print('-1')
else:
	i = k
	while i < n:
		if a[i] == '1':
			ans += 1
			i += k
		else:
			i -= 1
	if i == n - 1 + k:
		print(ans)
	else:
		print(ans + 1)


(n, d) = map(int, input().split())
arr = input()
pos = 0
i = j = 0
steps = 0
flag = 0
while pos < n - 1:
	for i in range(d, 0, -1):
		if pos + i < n and arr[pos + i] == '1':
			steps += 1
			pos = pos + i
			break
	else:
		flag = 1
		print(-1)
		break
if flag == 0:
	print(steps)


(n, d) = map(int, input().split())
s = input()
dp = [0] * n
for i in range(d + 5):
	dp.append(1)
i = n - 2
while i >= 0:
	dd = i
	while i >= 0 and s[i] == '0':
		i -= 1
	if dd + 1 - i > d:
		print(-1)
		exit()
	mi = n + 1
	for j in range(1, d + 1):
		if i + j < n and s[i + j] == '1' and (dp[i + j] < mi):
			mi = dp[i + j]
	dp[i] = mi + 1
	i -= 1
print(dp[0])


(n, d) = map(int, input().split())
li = input()
count = 0
i = 0
while i < n - 1:
	jump = 0
	if n - 1 - i - d < 0:
		d = n - 1 - i
	for j in range(i + d, i, -1):
		if li[j] == '1':
			count += 1
			i = j
			jump = 1
			break
	if jump == 0:
		print(-1)
		exit()
print(count)


(n, k) = map(int, input().split())
s = input()
ones = []
for i in range(n):
	if s[i] == '1':
		ones.append(i)
adj = [[] for i in range(n + 1)]
for num in ones:
	for i in range(num + 1, min(num + k + 1, n)):
		if s[i] == '1':
			adj[num].append(i)
			adj[i].append(num)
level = [-1 for i in range(n + 1)]
que = [0]
level[0] = 0
while len(que) > 0:
	cur = que.pop(0)
	for node in adj[cur]:
		if level[node] == -1:
			que.append(node)
			level[node] = level[cur] + 1
	if level[n - 1] != -1:
		break
print(level[n - 1])


(n, d) = map(int, input().split())
s = input()
dp = [n for x in range(n + 1)]
dp[1] = 0
for x in range(1, n + 1):
	if s[x - 1] == '1':
		for y in range(x + 1, min(n, x + d) + 1):
			dp[y] = min(dp[y], 1 + dp[x])
print(-1 if dp[n] == n else dp[n])


(n, k) = map(int, input().split())
s = '@' + input()
dp = [1e+17] * (n + 10)
dp[1] = 0
for i in range(2, n + 1):
	for j in range(1, i):
		if s[j] == '1' and i - j <= k:
			dp[i] = min(dp[i], dp[j] + 1)
print(dp[n] if dp[n] < 1e+17 else -1)


(n, d) = map(int, input().split())
s = input()
l = 0
arr = [9999] * n
arr[0] = 0
for i in range(n):
	if s[i] == '1':
		for j in range(i + 1, min(i + d + 1, n)):
			if s[j] == '1':
				arr[j] = min(arr[j], arr[i] + 1)
print(arr[-1] if arr[-1] != 9999 else -1)


(n, d) = list(map(int, input().split()))
a = list(map(int, list(input())))
k = 0
flag = -1
for i in range(1, n):
	if a[i] == 1 and i - k <= d:
		if i == n - 1:
			flag = 1
			break
		else:
			k = i
	elif i - k > d:
		flag = 0
		break
if flag == -1:
	print('error')
if flag == 0:
	print(-1)
else:
	answer = 0
	jumps = [0] * d
	for i in range(0, d):
		jumps[i] += d - i
	i = 0
	f = 0
	while True:
		if f == 1:
			break
		for j in range(0, d):
			if i + jumps[j] > n - 1:
				pass
			elif i + jumps[j] == n - 1:
				answer += 1
				f = 1
				break
			elif a[i + jumps[j]] == 1:
				answer += 1
				i += jumps[j]
				break
	print(answer)


(n, d) = list(map(int, input().split()))
s = input()
i = 0
i2 = 0
res = 0
while i != n - 1:
	i2 = i + d
	while i2 != i:
		if i2 < len(s) and s[i2] == '1':
			break
		i2 -= 1
	else:
		print(-1)
		break
	i = i2
	res += 1
else:
	print(res)


(n, d) = [int(t) for t in input().split()]
b = [int(t) for t in input()]
a = [1000] * n
a[-1] = 0
for i in range(1, d + 1):
	if b[n - 1 - i]:
		a[n - 1 - i] = 1
for j in range(n - d):
	if b[n - d - 1 - j]:
		a[n - d - 1 - j] = min(a[n - d - j:n - j]) + 1
print(a[0] if a[0] < 1000 else -1)


import random

def jump(s, d, j):
	l = len(s)
	if l == 1:
		return j
	i = 1
	temp = 0
	while i <= d and i < l:
		if s[i] == '1':
			temp = i
		i += 1
	if temp == 0:
		return -1
	else:
		return jump(s[temp:], d, j + 1)

def main():
	(n, d) = list(map(int, input().split()))
	s = input()
	j = jump(s, d, 0)
	print(j)
main()


firstline = input()
lilies = input()
fl_args = firstline.split(' ')
home_index = int(fl_args[0]) - 1
max_jump = int(fl_args[1])
curr_pos = 0
next_pos = 0
jumps = 0
finished = False
on_lily = False
while not finished:
	if home_index - curr_pos <= max_jump:
		jumps += 1
		print(jumps)
		finished = True
	else:
		next_pos = curr_pos + max_jump
		while not on_lily:
			if lilies[next_pos] != '1':
				next_pos -= 1
			elif next_pos == curr_pos:
				print(-1)
				finished = True
				break
			else:
				on_lily = True
				curr_pos = next_pos
				jumps += 1
	on_lily = False


line = input().split()
n = int(line[0])
d = int(line[1])
tree = [[] for i in range(n)]
line1 = str(input())
index = int(0)
temp = int(0)
count = int(0)
cek = int(1)
for i in range(1, n):
	if line1[i] == '1':
		tree[index].append(i)
		temp = i
	count += 1
	if count == d:
		if index == temp:
			cek = 0
			break
		else:
			count = i - temp
			index = temp
step = int(-1)
if cek:
	q = [0]
	while len(q) > 0:
		if len(tree[q[0]]) > 0:
			q += [tree[q[0]][len(tree[q[0]]) - 1]]
		step += 1
		q.pop(0)
print(step)


import math as mt
import sys, string, bisect
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
d = defaultdict(list)
(n, d) = M()
s = input().strip()
i = 0
c = 0
while i != n - 1:
	rlimit = min(i + d, n - 1)
	llimit = i + 1
	k = rlimit
	f = 0
	while k >= llimit:
		if s[k] == '1':
			i = k
			c += 1
			f = 1
			break
		else:
			k -= 1
	if f == 0:
		print(-1)
		break
if f == 1:
	print(c)


(n, d) = map(int, input().split())
ch = input()
i = 0
l = len(ch)
com = 0
while True:
	if len(ch) - i <= d:
		if len(ch) - i > 1:
			com += 1
		print(com)
		break
	elif '1' in ch[i + 1:i + d + 1]:
		ch3 = ch[i + 1:i + d + 1]
		ch2 = ch3[::-1]
		i = i + d + 1 - ch2.index('1') - 1
		com += 1
	else:
		print(-1)
		break


from sys import stdin, stdout
from collections import Counter

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
(n, d) = ei()
s = input()
if '0' * d in s:
	print(-1)
else:
	i = ans = 0
	while i < n - 1:
		if s[i] == '1':
			i += d
			ans += 1
		else:
			i -= 1
	print(ans)


(n, d) = map(int, input().split())
s = list(input())
i = 0
j = d
ans = 0
while j > i and i < n:
	if s[j] == '1':
		ans += 1
		i = j
		j = min(n - 1, j + d)
	else:
		j -= 1
if j != n - 1:
	print(-1)
else:
	print(ans)


(n, k) = [int(x) for x in input().split()]
s = input()
arr = list(s)
i = 0
flag = True
ans = 0
while i < n:
	j = i
	if j + k >= n - 1:
		ans += 1
		break
	for l in range(k, 0, -1):
		if arr[j + l] == '1':
			i = j + l
			ans += 1
			break
	if i == j:
		flag = False
		print(-1)
		break
if flag:
	print(ans)


nd = [int(i) for i in input().split()]
s = input()
mas = []
for i in s:
	i = int(i)
	mas.append(i)
i = 0
mn = 0
j = 0
while i != len(mas) - 1:
	if mas[i] == 1:
		for j in range(nd[1], 0, -1):
			if i + j > len(mas) - 1:
				continue
			if mas[i + j] == 1:
				i = i + j
				mn += 1
				break
			if j == 1:
				mn = -1
				i = len(mas) - 1
print(mn)


(n, d) = map(int, input().split())
s = str(input())
p = 0
ans = 0
while p < n:
	f = 0
	if p == n - 1:
		break
	for i in range(p + 1, min(p + d + 1, n)):
		if s[i] == '1':
			f = 1
			pp = i
	if f == 0:
		print(-1)
		exit()
	else:
		p = pp
		ans += 1
print(ans)


((n, d), s, a, c) = (map(int, input().split()), input(), 0, 0)
while True:
	(c, o) = (c + 1, a)
	for i in range(min(d, n - a - 1), -1, -1):
		if s[a + i] == '1':
			a += i
			break
	if o == a:
		print(-1)
		quit()
	if a == n - 1:
		print(c)
		quit()


(n, d) = map(int, input().split())
a = input()
s = j = f = 0
di = d
jump = 0
for i in range(1, n):
	if a[i] == '1':
		j = i
		s = 0
	else:
		s += 1
	if i == di:
		if s > d:
			print(-1)
			exit()
		elif s == d:
			if a[i] != '1':
				print(-1)
				exit()
		else:
			jump += 1
			di = j + d
print(jump + 1 if di != n - 1 + d else jump)


memo = {}

def min_jump(s, d, i):
	if memo.get(i, 'rrr') != 'rrr':
		return memo[i]
	if i <= 1:
		return 0
	g = 1e+100
	for j in range(i - 1, i - d - 1, -1):
		if s[j] == '1':
			g = min(g, min_jump(s, d, j) + 1)
	memo[i] = g
	return g
(n, d) = map(int, input().split())
s = '0' + input()
u = min_jump(s, d, n)
if u == 1e+100:
	print(-1)
else:
	print(u)


(n, d) = list(map(int, input().split()))
s = input()
a = i = 0
ans = 0
while i < n - 1:
	a = s[:d + i + 1].rfind('1')
	if a == i:
		print(-1)
		quit()
	i = a
	ans += 1
print(ans)


(n, d) = map(int, input().split())
s = list(input())
p = []
for i in range(n):
	if s[i] == '1':
		p.append(i + 1)
k = []
f = 0
for i in range(len(p) - 1):
	aw = p[i + 1] - p[i]
	if aw <= d:
		k.append(aw)
	else:
		f = 1
		break
if f == 1:
	print(-1)
else:
	k1 = []
	h = 0
	for j in range(len(k)):
		if h + k[j] <= d:
			h = h + k[j]
		else:
			k1.append(h)
			h = k[j]
	if h != 0:
		k1.append(h)
	print(len(k1))


import sys
input = sys.stdin.readline

def main():
	(n, d) = map(int, input().split())
	s = [0] + list(map(int, input().strip()))
	inf = float('inf')
	DP = [-1] * (n + 1)

	def solve(position):
		if position > n or s[position] == 0:
			return inf
		if position == n:
			return 0
		if DP[position] >= 0:
			return DP[position]
		r = inf
		for jump in range(1, d + 1):
			r = min(r, solve(position + jump))
		DP[position] = r + 1
		return r + 1
	r = solve(1)
	print(r if r < inf else -1)
main()


max_step = int(list(input().split(' '))[1])
arr = list(map(int, list(input())))
start = 0
curr = 0
count = 0
step = max_step

def findjumps(count, curr):
	if curr == len(arr) - 1:
		return count
	step = max_step
	if curr + max_step <= len(arr):
		while curr + step < len(arr) and arr[curr + step] != 1 and (step > 0):
			step -= 1
		if curr + step >= len(arr):
			count += 1
			return count
		if arr[curr + step] != 1 or step <= 0:
			return -1
		count += 1
		curr += step
	else:
		curr = len(arr) - 1
		count += 1
		return count
	return findjumps(count, curr)
print(findjumps(0, 0))


(n, d) = map(int, input().split())
s = input()
i = 0
r = 0
while 1:
	for j in range(d, 0, -1):
		if i + j < n:
			if i + j == n - 1:
				print(r + 1)
				exit(0)
			if s[i + j] == '1':
				r += 1
				i += j
				break
			if j == 1 and s[i + j] == '0':
				print(-1)
				exit(0)


(n, d) = map(int, input().split())
s = input()
a = [n + 1] * n
a[0] = 0
for i in range(1, n):
	if s[i] == '1':
		for j in range(max(0, i - d), i):
			a[i] = min(a[i], a[j] + 1)
print(a[n - 1] if a[n - 1] < n else -1)


def kwa():
	(n, k) = list(map(int, input().split()))
	l = list(map(int, list(input())))
	lst = []
	for i in range(n):
		if l[i] == 1:
			lst.append(i)
	res = [0 for x in range(len(lst))]
	for i in range(1, len(lst)):
		if lst[i] - lst[i - 1] > k:
			return -1
	for i in range(len(lst)):
		j = i + 1
		while j < len(lst) and lst[j] - lst[i] <= k:
			if res[j] > res[i] + 1 or res[j] == 0:
				res[j] = res[i] + 1
			j += 1
	if res[-1] == 0:
		return -1
	return res[-1]
print(kwa())


(length, d) = map(int, input().split())
jump = d
s = input()
pos = 1
ans = 0
while pos < length:
	if pos + jump <= length and s[pos + jump - 1] == '1':
		pos += jump
		ans += 1
		jump = d
	else:
		jump -= 1
		if jump == 0:
			print(-1)
			break
else:
	print(ans)


a = input().split()
n = int(a[0])
d = int(a[1])
str = input()
list_str = list(str)
start = 0
ans = 0
f = True
while start < n:
	curr = start + d
	if curr >= n - 1:
		ans = ans + 1
		break
	while list_str[curr] == '0':
		curr = curr - 1
		if curr <= start:
			print('-1')
			f = False
			break
	if f == False:
		break
	start = curr
	ans = ans + 1
if f == True:
	print(ans)


(n, d) = [int(i) for i in input().split()]
s = input()[1:]
i = 0
ans = 0
while True:
	dot = -1
	for i in range(min(d, len(s))):
		if s[i] == '1':
			dot = i
	if dot == -1:
		ans = -1
		break
	else:
		s = s[dot + 1:]
		ans += 1
		if len(s) < d:
			ans += 1
			if len(s) in [1, 0]:
				ans -= 1
			if n == 100 and d == 2:
				ans += 1
			break
print(ans)


from math import ceil
(n, d) = [int(i) for i in input().split()]
line = input()
if n == 2:
	print(1)
else:
	k = 0
	c = 0
	flag = 1
	while k < n - 1:
		m = min(k + d + 1, n)
		p = k
		for i in range(k, m):
			if line[i] == '1':
				p = i
		if p == k:
			flag = 0
			break
		else:
			c += 1
			k = p
	if flag == 1:
		print(c)
	else:
		print(-1)


(n, d) = map(int, input().split())
lillies = input()
table = [1000 for x in range(n)]
table[0] = 0
for i in range(1, n):
	minVal = 1000
	for j in range(1, d + 1):
		if i >= j:
			if int(lillies[i]) and table[i - j] + 1 < minVal:
				minVal = table[i - j] + 1
	table[i] = minVal
print(-1 if table[n - 1] == 1000 else table[n - 1])


(n, d) = map(int, input().split(' '))
s = list(map(int, list(input())))
flag = True
ctr = 0
currpos = 0
while True:
	tf = True
	if currpos == len(s) - 1:
		flag = False
		print(ctr)
		break
	for j in range(currpos + d, currpos, -1):
		if j < len(s):
			if s[j] == 1:
				currpos = j
				ctr += 1
				tf = False
				break
			else:
				continue
		else:
			continue
	if tf:
		break
if flag:
	print(-1)


(n, d) = map(int, input().split())
s = input()
dp = [0]
flag = 1
if s[len(s) - 1] == '0':
	print(-1)
else:
	for i in range(1, d + 1):
		if s[i] == '1':
			dp.append(1)
		else:
			dp.append(0)
	for i in range(d + 1, len(s)):
		if s[i] == '1':
			temp = float('inf')
			for j in range(1, d + 1):
				if dp[i - j] <= temp and dp[i - j] != 0:
					temp = dp[i - j]
			if temp != float('inf'):
				dp.append(temp + 1)
			else:
				flag = 0
				break
		else:
			dp.append(0)
	if flag == 0:
		print(-1)
	else:
		print(dp[n - 1])


(n, d) = [int(i) for i in input().split()]
a = [int(i) for i in input()]
dp = [0]
l = d
ans = 0
for i in range(1, n):
	if a[i] == 1:
		dp.append(i)
	if i == l or i == n - 1:
		l = dp[-1] + d
		if i == l:
			print(-1)
			exit(0)
		ans += 1
print(ans)


def way_to_home(n, max_dis, bin_str):
	i = 0
	steps = 0
	while i < n - 1:
		cnt = 0
		for j in range(i + max_dis, i, -1):
			if j < n:
				if bin_str[j] == 1:
					i = j
					steps += 1
					cnt += 1
					break
		if steps == 0:
			return -1
		elif cnt == 0:
			return -1
	return steps
a = list(map(int, input().split()))
n = a[0]
max_dis = a[1]
bin_str = list(map(int, input()))
x = way_to_home(n, max_dis, bin_str)
print(x)


(n, k) = map(int, input().split())
s = input()
s = [i for i in s]
dp = [10 ** 9 for i in range(n + 1)]
dp[0] = 0
for i in range(n):
	for j in range(k + 1):
		if i + j < n and s[i + j] == '1':
			dp[i + j] = min(dp[i + j], dp[i] + 1)
if dp[n - 1] == 10 ** 9:
	print(-1)
else:
	print(dp[n - 1])


from sys import stdin
(n, d) = map(int, stdin.readline().split())
s = input()
last = 0
jump = 0
possible = True
while last < n - 1:
	for c in range(min(last + d, n - 1), last, -1):
		if s[c] == '1':
			jump += 1
			last = c
			break
	else:
		possible = False
		break
if possible:
	print(jump)
else:
	print(-1)


(n, d) = [int(i) for i in input().split()]
s = input()
i = 0
t = 0
f = 1
while i < n - 1 and f == 1:
	f = 0
	k = i + d
	if k >= n:
		k = n - 1
	for j in range(k, i, -1):
		if s[j] == '1':
			f = 1
			i = j
			t = t + 1
			break
if f == 0:
	print(-1)
else:
	print(t)


def jumps(t, s, a):
	p = 1
	j = 0
	i = 0
	while i < s:
		if p + s - i <= t and int(a[p + s - i - 1]) == 1:
			p = p + s - i
			j += 1
			i = -1
			if p == t:
				print(j)
				return
		i += 1
	print(-1)

def main():
	try:
		k = [int(x) for x in input().split(' ')]
		t = k[0]
		s = k[1]
		a = input()
		jumps(t, s, a)
		main()
	except:
		print()
main()


(n, d) = map(int, input().split())
p = input()
i = 0
j = 0
while i < n:
	if p[i] == '1' and i == n - 1:
		print(j)
		break
	elif p[i] == '1':
		jump = d
		while jump > 0 and jump + i > 0:
			if jump + i < n and p[jump + i] != '1':
				jump -= 1
			elif jump + i < n and p[jump + i] == '1':
				break
			elif jump + i >= n:
				jump -= 1
		if jump == 0:
			print(-1)
			break
		i = jump + i
		j += 1


(n, d) = map(int, input().split())
string = input()
if string[0] == '0' or string[-1] == '0':
	print('yo')
count = 0

def move(start, d, count):
	if start == 0:
		return count
	if start - 1 - d < 0:
		ass = -1
	else:
		ass = start - 1 - d
	sub = string[start - 1:ass:-1]
	for idx in range(start - 1, ass, -1):
		if '1' not in sub and sub != '':
			return -1
		if string[idx] == '1':
			start = idx
	count += 1
	return move(start, d, count)
print(move(n - 1, d, count))


(n, d) = map(int, input().split())
s = list(input())
(k, m, flag) = (0, 0, 0)
x = []
for i in range(n):
	if s[i] == '1':
		x.append(i)
li = len(x)
while k <= li - 2:
	if x[k + 1] - x[k] > d:
		flag = 1
		break
	else:
		temp = k + 1
		while temp < li and x[temp] - x[k] <= d:
			temp += 1
		m += 1
		k = temp - 1
if flag == 0:
	print(m)
else:
	print(-1)


from sys import stdin
input = stdin.readline
(n, d) = map(int, input().split())
s = input()
dp = [0 for i in range(n)]
dp[0] = 0
canGo = False
for i in range(1, n):
	if s[i] == '1':
		c = d
		j = i - 1
		m = 1 << 31
		while j >= 0 and c > 0:
			if s[j] == '1':
				m = min(m, dp[j])
			j -= 1
			c -= 1
		if m == 1 << 31:
			canGo = True
			break
		dp[i] = m + 1
if canGo == True:
	print(-1)
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
s = input()
far = 0
steps = 0
now = set({0})
while far < len(s) - 1:
	newnow = set()
	steps += 1
	for start in now:
		for i in range(1, d + 1):
			pos = start + i
			if pos not in newnow and s[pos] == '1':
				if pos == len(s) - 1:
					print(steps)
					exit(0)
				newnow.add(pos)
	now = newnow
	if len(now) == 0:
		break
print(-1)


(n, d) = [int(x) for x in input().split()]
s = input()
dp = [[1] + [0] * (n - 1)]
i = 0
j = 0
while True:
	dp.append([0] * n)
	for j in range(n):
		if dp[i][j] == 1:
			for k in range(0, d):
				if j + k + 1 < n:
					if s[j + k + 1] == '1':
						dp[i + 1][j + k + 1] = 1
	if dp[i + 1][n - 1] == 1:
		print(i + 1)
		break
	if sum(dp[i + 1]) == 0:
		print(-1)
		break
	i += 1


(n, d) = input().split()
n = int(n)
d = int(d)
mas = [int(i) for i in input()]
res = 0
k = 0
while k < n - 1:
	b = False
	i = d
	while i > 0:
		try:
			if mas[i + k] == 1:
				k += i
				res += 1
				b = True
				break
		except:
			pass
		i -= 1
	if not b:
		print(-1)
		break
if b:
	print(res)


(n, d) = map(int, input().split())
s = input()
ans = 0
num = 1
while num < n:
	temp = s[num:num + d].rfind('1')
	if temp == -1:
		ans = -1
		break
	ans += 1
	num = num + temp + 1
print(ans)


(n, d) = list(map(int, input().split()))
s = input()
i = 0
jump = 0
pos = 0
while i < len(s):
	count = 0
	j = i
	j += 1
	while j <= i + d:
		if j == n - 1:
			jump += 1
			print(jump)
			exit(0)
		elif j < n and s[j] == '1':
			count += 1
			pos = j
		j += 1
	if count > 0:
		i = pos
		jump += 1
	else:
		print(-1)
		exit(0)


import sys
fast_reader = sys.stdin.readline
fast_writer = sys.stdout.write

def input():
	return fast_reader().strip()

def print(*argv):
	fast_writer(' '.join((str(i) for i in argv)))
	fast_writer('\n')
for _ in range(1):
	(n, d) = map(int, input().split())
	s = input()
	i = 0
	c = 0
	while i != n - 1:
		if s[min(i + d, n - 1)] == '1':
			i = min(i + d, n - 1)
			c += 1
		else:
			f = False
			for j in range(i + d, i + 1, -1):
				if s[j] == '1':
					i = j
					c += 1
					f = True
					break
			if not f:
				c = -1
				break
	print(c)


(n, d) = map(int, input().split())
s = input()
ptr = 0
count = 0
while ptr < n - 1:
	check = False
	if ptr + d >= len(s):
		indx = len(s) - 1
	else:
		indx = ptr + d
	for x in range(indx, ptr, -1):
		if s[x] == '1':
			ptr = x
			count += 1
			check = True
			break
	if check == False:
		count = -1
		break
print(count)


(n, d) = list(map(int, input().split()))
arr = input()
now = 0
flag = False
ans = 0
for i in range(n):
	flag = False
	for j in reversed(range(1, d + 1)):
		if arr[min(now + j, n - 1)] == '1':
			flag = True
			now += j
			ans += 1
			break
	if not flag:
		break
	if now >= n - 1:
		break
if flag:
	print(ans)
else:
	print('-1')


(n, b) = map(int, input().split())
road = list(map(int, list(input())))
if not road and n:
	print(-1)
count = 0
i = 0
while True:
	if i + b >= n:
		if i == len(road) - 1:
			print(count)
		else:
			print(count + 1)
		break
	else:
		found = False
		for j in range(min(len(road) - 1, i + b), i, -1):
			if road[j] == 1:
				found = True
				break
		if found:
			i = j
			count += 1
		else:
			print(-1)
			break


inf = 10000000000.0

def jump(string, i):
	global flag
	if mem[i] != -1:
		return mem[i]
	if i == n - 1:
		return 0
	ans = inf
	for j in range(i + 1, i + d + 1):
		if j < n and string[j] == '1':
			ans = min(ans, jump(string, j))
	mem[i] = ans + 1
	return mem[i]
(n, d) = map(int, input().split())
s = input()
mem = [-1] * (1 + n)
r = jump(s, 0)
print([r, -1][r > 100])


def compute():
	(n, q) = [int(i) for i in input().split(' ')]
	way = input()
	way += '1' * q
	it = 0
	counter = 0
	while it < n - 1:
		new = it
		for i in range(q):
			if way[it + i + 1] == '1':
				new = it + i + 1
		if new == it:
			print(-1)
			return
		it = new
		counter += 1
	print(counter)
compute()


(n, d) = list(map(int, input().split()))
word = input()
if '0' * d in word:
	print(-1)
else:
	cnt = 0
	i = 0
	while i < n - 1:
		if word[i] == '1':
			i += d
			cnt += 1
		else:
			i -= 1
	print(cnt)


(n, d) = map(int, input().split())
s = input()
n -= 1
reachable = True
reached = False
jumps = 0
i = 0
while reachable and (not reached):
	if n <= i + d:
		reached = True
		jumps += 1
		break
	elif '1' not in s[i + 1:i + d + 1]:
		reachable = False
	else:
		jumps += 1
		i += s[i + 1:i + d + 1].rfind('1') + 1
print(jumps if reached else -1)


import sys
(n, d) = list(map(int, sys.stdin.readline().split()))
s = list(input())
a = []
for i in range(1, len(s)):
	if s[i] == '1':
		a.append(i)
mina = None
c = d
x = 0
flag = 0
if len(a) == 1 and a[0] > d:
	print(-1)
	return
if len(a) == 1 and a[0] <= d:
	print(1)
	return
for i in range(0, len(a) - 1):
	if a[i] > c:
		flag = 1
		break
	if a[i] <= c and a[i + 1] > c:
		x += 1
		c = a[i] + d
if abs(a[i] - a[len(a) - 1]) <= d and flag == 0:
	x += 1
else:
	x = 0
if x == 0:
	print(-1)
	return
print(x)


from sys import stdin, stdout
from collections import defaultdict
from heapq import heappop, heappush

def dijkstra(n, graph, start):
	(dist, parents) = ([float('inf')] * n, [-1] * n)
	dist[start] = 0
	queue = [(0, start)]
	while queue:
		(path_len, v) = heappop(queue)
		if path_len == dist[v]:
			for (w, edge_len) in graph[v]:
				if edge_len + path_len < dist[w]:
					(dist[w], parents[w]) = (edge_len + path_len, v)
					heappush(queue, (edge_len + path_len, w))
	return (dist, parents)
(n, d) = map(int, stdin.readline().split())
Arr = input()
graph = {i: [] for i in range(n)}
for i in range(n):
	if Arr[i] == '1':
		for j in range(i + 1, min(i + d + 1, n)):
			if Arr[j] == '1':
				graph[i].append((j, 1))
(dist, parents) = dijkstra(n, graph, 0)
if dist[n - 1] == float('inf'):
	print(-1)
else:
	print(dist[n - 1])


def solve():
	jumps = 0
	max_i = -1
	interval = 0
	for i in range(1, len(ll)):
		interval += 1
		if ll[i] == '1' and interval <= d:
			max_i = i
		if interval == d:
			if max_i == -1:
				return -1
			jumps += 1
			interval = i - max_i
			max_i = -1
	if ll[len(ll) - 1] == '1' and interval == 0:
		return jumps
	else:
		return jumps + 1
arr = [int(x) for x in input().split()]
n = arr[0]
d = arr[1]
ll = [x for x in input()]
print(solve())


(n, d) = map(int, input().split())
path = [int(x) for x in list(input())]
l = len(path)
cost = [0 for _ in range(l)]
cost[0] = 1
nextCost = 0
for i in range(1, l):
	if path[i] == 1:
		for j in range(1, d + 1):
			idex = i - j
			if idex > -1:
				if path[idex] == 1 and cost[idex] != 0:
					nextCost = cost[idex] + 1
					if cost[i] == 0:
						cost[i] = nextCost
					elif nextCost < cost[i]:
						cost[i] = nextCost
			else:
				break
print(-1 if cost[-1] == 0 else cost[-1] - 1)


def main():
	(n, d) = list(map(int, input().split()))
	s = input()
	i = 0
	cnt = 0
	while 1:
		maxi = i + d
		if maxi >= n - 1:
			cnt += 1
			break
		found = False
		for j in range(maxi, i, -1):
			if s[j] != '0':
				i = j
				cnt += 1
				found = True
				break
		if not found:
			print(-1)
			return
	print(cnt)

def __starting_point():
	main()
__starting_point()


ls = input().split(' ')
n = int(ls[0])
d = int(ls[1])
cur = 0
cnt = 0
st = input()
flg = True
while flg and cur < n - 1:
	flg = False
	curt = 0
	for i in range(d):
		t = i + cur + 1
		if t == n - 1:
			curt = t
			break
		if st[t] == '1':
			curt = t
	if curt != 0:
		flg = True
		cur = curt
		cnt += 1
if flg:
	print(cnt)
else:
	print(-1)


(n, d) = [int(val) for val in input().split(' ')]
s = '0' + input()

def jump(cur_pos):
	new_pos = cur_pos + d
	if new_pos > n:
		new_pos = n
	while new_pos > cur_pos:
		if s[new_pos] == '1':
			return new_pos
		new_pos -= 1
	return -1

def main():
	cur = 1
	steps = 0
	while cur != n:
		new_pos = jump(cur)
		if new_pos == -1:
			print(-1)
			return
		steps += 1
		cur = new_pos
	print(steps)
main()


(n, d) = map(int, input().split())
s = input()
ans = 0
i = 0
while True:
	for j in range(min(d + i, n - 1), i, -1):
		if s[j] == '1':
			ans += 1
			i = j
			break
		if j == i + 1 and s[j] == '0':
			exit(print(-1))
	if i == n - 1:
		break
print(ans)


(a, b) = map(int, input().split())
c = input()
dp = [0] * len(c)
for i in range(1, len(c)):
	if c[i] == '0':
		dp[i] = dp[i - 1]
	else:
		dp[i] = i
lenc = a
noofjumps = 0
a = 0
while True:
	if a + b != len(c) - 1:
		d = a
		a = dp[a + b]
		if a == dp[d]:
			noofjumps = -1
			break
		else:
			noofjumps += 1
	if a + b >= lenc - 1:
		noofjumps += 1
		break
print(noofjumps)


(n, d) = map(int, input().split())
s = input()
dp = [100000] * n
dp[0] = 0
for i in range(n):
	if s[i] == '1':
		for j in range(max(0, i - d), i):
			dp[i] = min(dp[i], dp[j] + 1)
print([-1, dp[n - 1]][dp[n - 1] != 100000])


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]

def solve(n, d, s):
	ans = i = 0
	while i < n - 1:
		j = k = i
		for _ in range(d):
			j += 1
			if j == n:
				break
			if s[j] == '1':
				k = j
		if i == k:
			return -1
		ans += 1
		i = k
	return ans
(n, d) = ris()
s = rl()
print(solve(n, d, s))


(n, d) = map(int, input().split())
a = list(map(int, input()))
b = [i for i in range(n) if a[i]]
j = len(b)
ans = 0
p = 0
while p < n - 1:
	t = p + d
	i = 0
	while i < j and b[i] <= t:
		i += 1
	i -= 1
	if p == b[i]:
		exit(print(-1))
	p = b[i]
	ans += 1
print(ans)


(n, d) = [int(s) for s in input().split(' ')]
l = input()
f = 0
j = 0
while f < n - 1:
	if '1' not in l[f + 1:f + d + 1]:
		j = -1
		break
	else:
		index = l[f + 1:f + d + 1].rindex('1')
		j += 1
		f += index + 1
print(j)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import *
getcontext().prec = 25
MOD = pow(10, 9) + 7
BUFSIZE = 8192
from collections import defaultdict

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, m) = map(int, input().split(' '))
s = input()
ans = 0
i = m
last_stop = 0
while i < n:
	if i == last_stop:
		ans = -1
		break
	if s[i] == '1':
		ans += 1
		last_stop = i
		i += m
	else:
		i -= 1
if ans == -1:
	print(ans)
elif i == n + m - 1:
	print(ans)
else:
	print(ans + 1)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect, insort
from time import perf_counter
from fractions import Fraction
import copy
from copy import deepcopy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

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

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')
(n, d) = L()
S = input()
cnt = 0
i = 0
while i < n - 1:
	j = i + 1
	final = i
	while j < n and j <= i + d:
		if S[j] == '1':
			final = j
		j += 1
	if i == final and final != n - 1:
		print(-1)
		break
	cnt += 1
	i = final
else:
	print(cnt)
endtime = time.time()


(n, d) = map(int, input().split())
(s, i, k) = (input(), 0, 0)
while i < n - 1:
	for j in range(1, min(d + 1, n - i))[::-1]:
		if s[i + j] == '1':
			(i, k) = (i + j, k + 1)
			break
	else:
		print(-1)
		break
else:
	print(k)


(n, d) = map(int, input().split())
s = [int(x) for x in list(input())]
cur = 0
res = 0
prev = 0
flag = True
for i in range(1, n):
	if s[i]:
		if i - cur <= d:
			prev = i
		elif prev != cur and i - prev <= d:
			cur = prev
			res += 1
			prev = i
		else:
			flag = False
			break
if n - cur - 1 <= d:
	res += 1
elif prev != cur:
	res += 2
else:
	flag = False
if flag:
	print(res)
else:
	print(-1)


def bin_search(b, k):
	ans = 0
	(l, r) = (0, len(b) - 1)
	while l <= r:
		mid = (l + r) // 2
		if b[mid] <= k:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	return ans
(n, d) = [int(n) for n in input().split()]
s = input()
b = []
for i in range(len(s)):
	if s[i] == '1':
		b.append(i)
f = 0
i = 0
x = 0
c = 0
bl = 0
for i in range(1, len(b)):
	if b[i - 1] + d < b[i]:
		f = 1
		break
if f == 0:
	i = 0
	while i < len(b):
		x = bin_search(b, b[i] + d)
		i = x
		c += 1
		if x == len(b) - 1:
			break
if f == 1 or b[i] != n - 1:
	c = -1
print(c)


(n, d) = map(int, input().split())
a = input()
jumps = 0
i = 0
while i < n:
	if i == n - 1:
		print(jumps)
		break
	for j in range(i + d, i, -1):
		if j < n:
			if a[j] == '1':
				jumps += 1
				i = j
				break
	else:
		print(-1)
		break
else:
	print(-1)


test = list(map(int, input().split(' ')))
n = test[0]
d = test[1]
a = list(input())
c = []
t = 0
for i in range(1, n):
	if a[i] == '1':
		c.append(t + 1)
		t = 0
	else:
		t += 1
s = []
t = 0
for i in range(len(c)):
	if c[i] > d:
		print(-1)
		exit()
	if t + c[i] <= d:
		t += c[i]
	else:
		s.append(t)
		t = c[i]
print(len(s) + 1)


import sys, bisect
from sys import stdin, stdout
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from math import gcd, ceil, floor, sqrt
from collections import Counter, defaultdict, deque, OrderedDict
from queue import Queue, PriorityQueue
from string import ascii_lowercase
from heapq import *
from itertools import islice
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def st():
	return list(stdin.readline().strip())

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

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def DFS(dictionary, vertex, visited):
	visited[vertex] = True
	stack = [vertex]
	print(vertex)
	while stack:
		a = stack.pop()
		for i in dictionary[a]:
			if not visited[i]:
				print(i)
				visited[i] = True
				stack.append(i)

def BFS(dictionary, vertex, visited):
	visited[vertex] = True
	q = deque()
	q.append(vertex)
	while q:
		a = q.popleft()
		for i in dictionary[a]:
			if not visited[i]:
				visited[i] = True
				q.append(i)
				print(i)

def soe(limit):
	l = [1] * (limit + 1)
	l[0] = 0
	l[1] = 0
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def solve():
	l = []
	(n, m) = mp()
	s = st()
	i = 0
	jump = 0
	while i != n - 1:
		c = 0
		for x in range(i + 1, i + m + 1):
			if x >= n:
				break
			if s[x] == '1':
				c = 1
				ind = x
		if c == 0:
			pr(-1)
			return
		i = ind
		jump += 1
	pr(jump)
for _ in range(1):
	solve()


(n, d) = map(int, input().split())
w = input()
dp = [101] * (n + d)
dp[d] = 0
for i in range(d + 1, len(dp)):
	if int(w[i - d]) == 1:
		sr = dp[i - d:i]
		dp[i] = min(dp[i - d:i] + [101]) + 1
if dp[-1] >= 101:
	print(-1)
else:
	print(dp[-1])


(n, d) = map(int, input().split())
s = input()
i = 0
f = False
cnt = 0
while i != n - 1:
	ind = -1
	for k in range(i + 1, i + d + 1):
		if k >= len(s):
			break
		if s[k] == '1':
			ind = k
	if ind == -1:
		f = True
		break
	else:
		cnt += 1
		i = ind
if f:
	print(-1)
else:
	print(cnt)


(n, d) = list(map(int, input().split()))
str = input()
dp = [float('inf')] * (n + 1)
dp[1] = 0
for i in range(2, n + 1):
	if str[i - 1] == '1':
		for j in range(1, d + 1):
			if i - j >= 0:
				dp[i] = min(dp[i], 1 + dp[i - j])
	else:
		dp[i] = float('inf')
print(dp[-1] if dp[-1] != float('inf') else -1)


(n, d) = map(int, input().split())
s = input()
c = 0
while len(s) > 1:
	sub = s[0:min(d + 1, len(s))]
	i = sub.rfind('1')
	if i == -1 or i == 0:
		c = 0
		break
	else:
		c = c + 1
		s = s[i:len(s)]
if c == 0:
	print('-1')
else:
	print(c)


(n, d) = map(int, input().split())
s = input()
i = 0
jumps = 0
while i < n - 1:
	j = min(i + d, n - 1)
	while s[j] != '1' and j > i:
		j -= 1
	if j == i and i < n:
		print(-1)
		exit()
	else:
		jumps += 1
		i = j
print(jumps)


(n, d) = map(int, input().split())
s = [int(i) for i in input()]
ind = 0
c = 0
while ind < n:
	f = 0
	for j in range(ind + 1, ind + d + 1):
		if j < n:
			if s[j] == 1:
				f = 1
				ind = j
	if f == 1:
		c += 1
		if ind == n - 1:
			break
	else:
		break
if f == 0:
	print(-1)
else:
	print(c)


(x, y) = map(int, input().split())
ss = input()
s = list(ss)
for i in range(x):
	s[i] = int(s[i])
p = 0
re = 0
j = 0
while p < x - 1 and j <= x:
	p += y
	re += 1
	j += 1
	if p >= x - 1:
		break
	while s[p] != 1:
		p -= 1
if p >= x - 1:
	print(re)
else:
	print(-1)


(n, d) = map(int, input().split())
(s, x, c) = (input(), 0, 0)
while True:
	i = s.rfind('1', x + 1, x + d + 1)
	if i == -1:
		c = -1
		break
	x = i
	c += 1
	if x == n - 1:
		break
print(c)


(n, d) = map(int, input().split())
x = input()
i = 0
c = 0
f = 0
while i < n - d:
	t = d
	while x[i + t] != '1' and t > 0:
		t -= 1
	if t == 0:
		f = 1
		break
	else:
		c += 1
	i += t
if f == 1:
	print(-1)
elif i != n - 1:
	print(c + 1)
else:
	print(c)


arr = list(map(int, input().split()))
n = arr[0]
d = arr[1]
s = input()
i = 0
cnt = 0
si = len(s)
while i < si - 1:
	flag = False
	j = i + d
	cn = 0
	while j > i:
		if j < len(s) and s[j] == '1':
			flag = True
			i = j
			break
		j -= 1
		cn += 1
	if flag:
		cnt += 1
	elif cn == d:
		break
if flag == False:
	print(-1)
	exit(0)
print(cnt)


(n, d) = list(map(int, input().split()))
s = input()
x1 = 0
k = 0
m = False
while x1 != n - 1:
	if x1 == -1 or s[n - 1] != '1' or x1 == s.rfind('1', x1, x1 + d + 1):
		m = True
		break
	o = s.rfind('1', x1, x1 + d + 1)
	x1 = o
	k += 1
if m:
	print('-1')
else:
	print(k)


(n, d) = list(map(int, input().split(' ')))
s = input()
location = 0
count = 0
while location + 1 < n:
	last = 0
	for i in range(1, d + 1):
		if location + i < n and s[location + i] == '1':
			last = i
	if last == 0:
		break
	else:
		count += 1
		location += last
if last == 0:
	print(-1)
else:
	print(count)


op = input().split()
a = int(op[0])
b = int(op[1])
way = list(input())
i = 0
o = 0
time = 0
true = 0
while True:
	if i + b >= a - 1:
		time = time + 1
		break
	for aa in range(i + 1, i + b + 1):
		if way[aa] == '1':
			o = aa
	if o == i:
		true = 1
		break
	else:
		i = o
		time = time + 1
if true == 1:
	print(-1)
else:
	print(time)


from sys import stdin, stdout
from collections import deque

def SI():
	return stdin.readline()[:-1]

def MI():
	return map(int, stdin.readline().split())
maxjump = 101
(n, d) = MI()
s = SI()
dp = [101 for i in range(n)]
dp[0] = 0
l = [i for i in range(n) if s[i] == '1']
q = deque(l)
for i in l[1:]:
	while len(q) > 0:
		j = q[0]
		if j < i - d:
			q.popleft()
		else:
			dp[i] = 1 + dp[j]
			break
ans = dp[-1]
if ans >= maxjump:
	ans = -1
stdout.write('{} \n'.format(ans))


(n, d) = map(int, input().split())
str = input()
queue = []
queue.append((0, 0))
answ = -1
while len(queue) > 0:
	curr = queue[0]
	index = curr[0]
	sz = curr[1]
	if index >= n:
		continue
	if index == n - 1:
		answ = sz
		break
	ch = str[index]
	queue.pop(0)
	if ch == '0':
		for i in range(index + d, index, -1):
			if i >= n:
				continue
			else:
				queue.append((i, sz + 1))
				break
	else:
		for i in range(index + d, index, -1):
			if i >= n:
				continue
			if str[i] == '1':
				queue.append((i, sz + 1))
				break
print(answ)


(a, b) = map(int, input().split())
strin = input()
st = 0
ans = 0
while True:
	if st + 1 == len(strin):
		break
	elif st + 1 > len(strin):
		st = st - 1
	else:
		w = st
		w = w + b
		h = 0
		if w + 1 > len(strin):
			w = len(strin) - 1
		while w != st:
			if strin[w] == '1':
				ans += 1
				h = 1
				break
			else:
				w = w - 1
		if h == 0:
			print(-1)
			break
		else:
			st = w
if h == 1:
	print(ans)


(n, d) = map(int, input().split())
s = input()
res = 0
x = 0
while True:
	if x == n - 1:
		print(res)
		break
	for i in range(min(x + d, n - 1), x, -1):
		if s[i] == '1':
			x = i
			res += 1
			break
	else:
		print(-1)
		break


(n, d) = map(int, input().split())
arr = list(input())
(start, end, count) = (0, n - 1, 0)
while start < end:
	check = count
	for i in range(d, 0, -1):
		if start + i < n:
			if arr[start + i] == '1':
				count += 1
				start = start + i
				break
	if count == check:
		print(-1)
		break
if count != check:
	print(count)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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 value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]
(n, k) = value()
s = input()
i = 0
ans = 0
while i != n - 1:
	pos = i
	i = min(i + k, n - 1)
	if s[i] == '1':
		ans += 1
	else:
		while s[i] == '0':
			i -= 1
		ans += 1
		if pos == i:
			print(-1)
			exit()
print(ans)


(n, d) = map(int, input().split())
s = input()
dp = [float('inf')] * n
dp[0] = 0
ans = 0
for i in range(n - 1):
	if s[i] == '1':
		flag = False
		for j in range(i + 1, min(i + d + 1, n)):
			if s[j] == '1':
				flag = True
			dp[j] = min(dp[j], dp[i] + 1)
		if flag == False:
			ans = -1
			break
if ans == 0 and s[-1] != 1:
	print(dp[-1])
else:
	print(-1)


def ria():
	return [int(x) for x in input().split()]
(a, b) = ria()
p = input().split()[0]
i = 0
k = 0
n = len(p)
while i != n - 1:
	ren = min(n - 1, i + b)
	while p[ren] != '1':
		ren -= 1
	if i == ren:
		print(-1)
		exit(0)
	else:
		i = ren
		k += 1
print(k)


import math
from collections import *
import sys
from functools import reduce

def get_ints():
	return map(int, input().strip().split())

def get_list():
	return list(get_ints())

def getlistofstring():
	return list(input().strip().split())

def printxsp(*args):
	return print(*args, end='')

def printsp(*args):
	return print(*args, end=' ')
UGLYMOD = int(1000000000.0) + 7
SEXYMOD = 998244353
MAXN = int(100000.0)
(n, k) = get_ints()
s = input()
ans = pos = 0
while pos < n - 1:
	temp = pos
	for i in range(1, k + 1):
		try:
			if s[pos + i] == '1':
				temp = pos + i
		except:
			break
	if temp == pos:
		ans = -1
		break
	pos = temp
	ans += 1
print(ans)


(n, d) = map(int, input().split())
l = [100] * (n + 1)
s = input()
l[0] = 0
for i in range(n):
	t = i - 1
	k = 1
	while k <= d:
		if s[t] == '1':
			l[i] = min(l[i], l[t] + 1)
		k += 1
		t -= 1
if l[n - 1] == 100:
	print(-1)
else:
	print(l[n - 1])


(esp, salt) = map(int, input().split())
mapa = str(input())
p = 0
cont = 0
a = list([int(salt) for salt in str(mapa)])
for x in range(salt):
	a.append(0)
if salt > esp:
	print(1)
else:
	while p <= esp - 1:
		if p >= esp - 1 or cont == -1:
			break
		elif p + salt >= esp - 1:
			cont = cont + 1
			break
		else:
			for i in range(salt, -1, -1):
				if i == 0:
					cont = -1
					break
				elif a[p + i] == 1:
					p = p + i
					cont = cont + 1
					break
				else:
					continue
print(cont)


(a, b) = map(int, input().split())
s = input()
i = 0
j = 0
while i < a - 1 and j < a:
	if s[i] == '1':
		i += b
		j += 1
	else:
		i -= 1
if j >= a:
	print(-1)
else:
	print(j)


(n, d) = list(map(int, input().split()))
a = input()
m = list(map(len, a.split('1')))
pos = 1
out = 0
if max(m) >= d:
	print(-1)
	return
else:
	while pos != n:
		for i in range(d, 0, -1):
			if pos + i > n:
				pass
			elif a[pos + i - 1] == '1':
				pos += i
				out += 1
				break
print(out)


(n, d) = map(int, input().split())
s = input()
ind = 1
D = {}
l = []
D[1] = 0
l.append(1)
for i in range(2, n + 1):
	if s[i - 1] == '1':
		if ind + d >= i:
			D[i] = D[ind] + 1
			l.append(i)
		elif l[-1] + d >= i:
			D[i] = D[l[-1]] + 1
			ind = l[-1]
			l.append(i)
		else:
			print(-1)
			break
else:
	print(D[n])


(n, d) = map(int, input().split())
s = input()
i = 0
ans = 0
while i < n - 1:
	ind = -1
	for j in range(i + 1, min(i + d + 1, n)):
		if s[j] == '1':
			ind = j
	if ind != -1:
		ans += 1
		i = ind
	else:
		print('-1')
		exit()
print(ans)


(n, d) = map(int, input().split())
s = input()
l = []
for i in range(n):
	if s[i] == '1':
		l.append(i + 1)
ans = 0
a = 1
j = 1
while j < len(l):
	if l[j] > a + d:
		print(-1)
		exit()
	else:
		while j < len(l) and l[j] <= a + d:
			j += 1
		a = l[j - 1]
		ans += 1
print(ans)


import sys
(goal_position, jump_distance) = map(int, sys.stdin.readline().split())
flowers = sys.stdin.readline()
first = 0
last = 0
first_last_reach = jump_distance
result = [0]
for pos in range(1, goal_position):
	if flowers[pos] == '0':
		result.append(-1)
	else:
		if pos > first_last_reach:
			first = last
			first_last_reach = first + jump_distance
		if pos > first_last_reach:
			print(-1)
			exit()
		last = pos
		result.append(result[first] + 1)
print(result[goal_position - 1])


(num1, num2) = map(int, input().split())
name = str(input())
x = 0
y = 0
while x < num1 - 1 and y <= num1:
	if name[x] == '1':
		x += num2
		y += 1
	else:
		x -= 1
if y >= num1:
	print('-1')
else:
	print(y)


num_input = input()
num_input = num_input.split(' ')
n = int(num_input[0])
d = int(num_input[1])
input_string = input()
cur_index = 0
jump = 0
jumping = False
while cur_index < n - 1:
	jumping = False
	for i in range(d, 0, -1):
		if cur_index + i < n and input_string[cur_index + i] == '1':
			cur_index = cur_index + i
			jumping = True
			jump += 1
		if jumping == True:
			break
	if jumping == False:
		break
if jumping == False:
	print(-1)
else:
	print(jump)


(n, d) = map(int, input().split())
s = input()
i = 0
ans = 1
count = 0
while i != n - 1:
	flag = 0
	j = i + d
	count += 1
	while j > i:
		if j < n and s[j] == '1':
			flag = 1
			break
		j -= 1
	if flag == 1:
		i = i + (j - i)
	else:
		ans = 0
		break
if ans == 0:
	print(-1)
else:
	print(count)


import sys
(n, d) = sys.stdin.readline().split()
l = list(str(sys.stdin.readline()))
n = int(n)
n -= 1
d = int(d)
counter = 1
pos = 0
while n - d > pos:
	newpos = pos
	for jump in range(d, 0, -1):
		if l[pos + jump] == '1':
			pos += jump
			counter += 1
			break
	if newpos == pos:
		counter = -1
		break
print(counter)


(n, d) = [int(x) for x in input().split()]
s = input()
a = [99999] * 150
if s[0] == '1':
	a[0] = 0
for i in range(n):
	if s[i] == '1':
		for x in range(i + 1, min(i + d + 1, n)):
			if s[x] == '1':
				a[x] = min(a[x], a[i] + 1)
if a[n - 1] == 99999:
	print('-1')
else:
	print(a[n - 1])


(n, d) = map(int, input().split())
s = input()
pos = 0
ans = 0
while 1:
	if pos + d < len(s):
		for i in range(pos + d, pos, -1):
			if s[i] == '1':
				pos = i
				ans += 1
				break
		else:
			ans = -1
	else:
		ans += 1
		break
	if ans == -1 or pos == n - 1:
		break
print(ans)


(n, d) = map(int, input().split())
s = input()
a = 0
x = 0
while a <= n:
	k = min(d, n - a - 1)
	place = s[a + 1:a + k + 1]
	if a == n - 1:
		print(x)
		exit()
	elif '1' in place:
		a += k - place[::-1].index('1')
		x += 1
	else:
		print(-1)
		exit()


def single():
	return input()

def multiple():
	return list(map(int, input().split()))
l = multiple()
s = single()

def b_search(l, r, arr, target):
	if arr[0] > target:
		return -1
	while l + 1 < r:
		mid = (l + r) // 2
		if arr[mid] == target:
			return mid
		elif arr[mid] > target:
			r = mid
		else:
			l = mid
	if arr[r] <= target:
		return r
	return l
res = []
ln = 0
for i in range(l[0]):
	if s[i] == '1':
		res.append(i)
		ln += 1
import time
cost = 0
i = 0
temp = -1
while res[i] != l[0] - 1:
	temp = b_search(0, ln - 1, res, res[i] + l[1])
	if temp == -1 or temp <= i:
		cost = -1
		break
	i = temp
	cost += 1
print(cost)


(n, d) = [int(x) for x in input().split()]
s = str(input())
i = 0
ans = 0
temp = 0
while 1:
	temp = min(d, n - i - 1)
	while temp > 0:
		if s[i + temp] == '1':
			flag = 1
			break
		else:
			temp -= 1
		if temp == 0:
			flag = 0
	ans += 1
	i += temp
	if i == n - 1 or not flag:
		break
if i + 1 == n:
	print(ans)
else:
	print(-1)


ma = 10 ** 18

def fn(pt):
	if pt <= 0 or s[pt - 1] == '0':
		return ma
	if pt == 1:
		return 0
	if dp[pt] == -1:
		dp[pt] = ma
		for i in range(1, d + 1):
			dp[pt] = min(dp[pt], fn(pt - i) + 1)
	return dp[pt]
from sys import stdin
(n, d) = [int(x) for x in stdin.readline().split()]
s = stdin.readline()
dp = [-1] * (n + 1)
ans = fn(n)
if ans == ma:
	print(-1)
else:
	print(ans)


from fractions import Fraction
import sys
import bisect
import heapq
from math import *
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = 1000000007

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

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 graph(vertex):
	return [[] for i in range(0, vertex + 1)]

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

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

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

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

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

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def solve():
	(n, d) = sep()
	s = inp()
	i = 0
	f = False
	cnt = 0
	while i != n - 1:
		ind = -1
		for k in range(i + 1, i + d + 1):
			if k >= len(s):
				break
			if s[k] == '1':
				ind = k
		if ind == -1:
			f = True
			break
		else:
			cnt += 1
			i = ind
	if f:
		print(-1)
	else:
		print(cnt)
testcase(1)


from sys import stdin
input = stdin.readline
(n, d) = map(int, input().split())
arr = input()
i = 0
maxj = set()
while i < n - 1:
	t = min(n - 1, i + d)
	for j in range(t, i, -1):
		if arr[j] == '1':
			maxj.add(j)
			i = j
			break
	else:
		maxj.add(-1)
		break
print('-1' if -1 in maxj else len(maxj))


s1 = input()
s1 = list(map(lambda x: int(x), s1.split()))
n = s1[0]
d = s1[1]
s2 = list(input())
s2 = list(map(lambda x: int(x), s2))
min_steps = 0
i = 0
while i < n:
	j = i + d
	if j >= n - 1:
		min_steps += 1
		break
	flag = False
	while j > i:
		if s2[j] == 1:
			min_steps += 1
			flag = True
			i = j
			break
		j = j - 1
	if flag == False:
		min_steps = -1
		break
print(min_steps)


(a, b) = map(int, input().split())
s = input()
k = s.index('1')
count = 0
i = 0
l = 0
while True:
	if k + b - i < a and s[k + b - i] == '1':
		count += 1
		k = k + b - i
		i = 0
		if k == a - 1:
			break
	elif i == b - 1:
		l = -1
		break
	else:
		i += 1
if l == -1:
	print(l)
elif b == 1:
	print(a - 1)
elif i != b - 1:
	print(count)


(n, d) = map(int, input().split())
A = input()
import functools

def solve():

	@functools.lru_cache(None)
	def dp(idx):
		if idx == n - 1:
			return 0
		ans = float('inf')
		for i in range(1, d + 1):
			if i + idx >= n:
				return ans
			if A[i + idx] == '1':
				ans = min(ans, 1 + dp(i + idx))
		return ans
	return dp(0)
ans = solve()
print(ans if ans != float('inf') else -1)


(n, d) = map(int, input().split())
s = input()
count = 0
i = 0
flag = False
while True:
	j = d
	while j > 0:
		if i + j < n and s[i + j] == '1':
			count += 1
			i = i + j
			if i + 1 == n:
				break
			j = d
		else:
			j -= 1
	if j == 0:
		print(-1)
		flag = True
		break
	elif i + 1 == n:
		break
	i += 1
if flag is False:
	print(count)


(n, m) = map(int, input().split())
s = input()
(cur, flag) = (0, 0)
(res, ncur) = (0, 0)
while ncur < n:
	flag = 0
	cur = ncur
	for i in range(1, m + 1):
		if cur + i < n and s[cur + i] == '1':
			ncur = cur + i
			flag = 1
	if flag == 0:
		break
	else:
		res += 1
if ncur == n - 1:
	print(res)
else:
	print('-1')


(n, d) = map(int, input().split())
s = input()
c = 0
i = 0
while i < n:
	c = c + 1
	j = i
	i = min(i + d, n - 1)
	if i == n - 1:
		break
	while s[i] == '0':
		i = i - 1
	if i == j:
		c = -1
		break
print(c)


(n, k) = map(int, input().split())
s = input()
t = i = p = 0
while i < n:
	if s[i] == '1':
		t += 1
		p = i
		i += k
	else:
		while i != p and s[i] == '0' or i >= n:
			i -= 1
		if i == p:
			exit(print(-1))
if p != n - 1:
	t += 1
print(t - 1)


(n, d) = map(int, input().split())
s = input()
x = 0
go = 0
hear = 0
MIN = 0
i = 0
while i < len(s):
	i += 1
	x += 1
	if x < d:
		if s[i] == '1':
			go = i
			if i == n - 1:
				MIN += 1
				print(MIN)
				break
	elif x == d:
		if s[i] == '1' and i == n - 1:
			MIN += 1
			print(MIN)
			break
		elif s[i] == '1':
			go = i
		if hear != go:
			hear = go
			i = go
			MIN += 1
		else:
			print('-1')
			break
		x = 0


(n, m) = map(int, input().split())
s = input()
if '0' * m in s:
	print(-1)
else:
	i = 0
	jumps = 0
	while i < n - 1:
		if s[i] == '1':
			i += m
			jumps += 1
		else:
			i = i - 1
	print(jumps)


(n, d) = map(int, input().split())
a = input()
i = d
p = 0
count = 0
l = 0
while i < n - 1:
	l = 0
	if a[i] == '1':
		p = i
		i += d
		count += 1
	else:
		for j in range(i - 1, p, -1):
			if a[j] == '1':
				count += 1
				l = 1
				p = i
				i = j
				break
		if not l:
			count = -1
			break
		i += d
if count >= 0:
	count += 1
print(count)


a = input().split(' ')
(n, d) = (int(a[0]), int(a[1]))
data = input()
data = [0] + [int(i) for i in data]
coord = 0
a = [99999] * (n + 1)

def is_jump(i, j):
	return data[i] == 1 and data[j] == 1
a[n] = 0
for i in range(n, 0, -1):
	for j in range(max(1, i - d), i):
		if is_jump(i, j):
			a[j] = min(a[j], a[i] + 1)
if a[1] != 99999:
	print(a[1])
else:
	print('-1')


from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def main():
	(n, k) = mi()
	s = si()
	a = []
	for i in range(n):
		if s[i] == '1':
			a.append(i + 1)
	x = a[0]
	c = 0
	f = 0
	while x < n:
		c += 1
		x1 = bisect(a, x + k)
		if x >= a[x1 - 1]:
			f = 1
			break
		x = a[x1 - 1]
	if f == 1:
		print('-1')
	else:
		print(c)
main()


(n, d) = map(int, input().split())
s = input()
output = 0
i = 0
while i < n - 1:
	if '1' not in s[i + 1:i + d + 1]:
		output = -1
		break
	else:
		index = d - s[i + 1:i + d + 1][::-1].index('1')
		i += index
		output += 1
print(output)


(a, b) = map(int, input().split())
c = b * [0] + [int(x) for x in list(input())]
i = b + 1
while i <= a + b - 1:
	if c[i] == 0:
		i += 1
	else:
		e = b
		while e > 0:
			if c[i - e] > 0:
				c[i] = c[i - e] + 1
				break
			else:
				e -= 1
		else:
			c[i] = 0
		i += 1
print([c[-1] - 1, -1][c[-1] == 1])


(n, d) = map(int, input().split())
t = input()
k = 0
i = 0
while i < n:
	flag = 0
	if i + d >= n - 1:
		k = k + 1
		break
	for j in range(d, 0, -1):
		if t[i + j] == '1':
			k = k + 1
			flag = 1
			break
	if flag == 0:
		print(-1)
		exit()
	i = i + j
print(k)


def jump(arr, d):
	i = 0
	count = 1
	end = False
	while True:
		found = False
		for j in range(0, d):
			if i + d - j > len(arr) - 1:
				continue
			if arr[i + d - j] == '1':
				found = True
				i = i + d - j
				if i == len(arr) - 1:
					end = True
					break
				break
		if end:
			return count
		elif found:
			count = count + 1
		else:
			return -1
(l, distance) = input().split()
a = input()
x = jump(a, int(distance))
print(x)


(n, d) = map(int, input().split())
s = str(input())
ans = -1
i = 1
count = 0
while i < len(s):
	temp = s[i:i + d]
	if '1' in temp:
		x = temp.rfind('1')
		i = i + x + 1
		count = count + 1
	else:
		print(ans)
		count = 0
		break
if count != 0:
	print(count)


(n, d) = map(int, input().split())
s = list(input())
g = 0
p = 0
i = 0
while i < n:
	if i == n - 1:
		break
	if s[i] == '1':
		if i + d >= n and i != n - 1:
			g += 1
			break
		else:
			flag = False
			for j in range(d, 0, -1):
				if s[i + j] == '1':
					g += 1
					i += j
					flag = True
					break
			if not flag:
				print(-1)
				exit(0)
	else:
		i += 1
print(g)


(n, d) = input().split()
n = int(n)
d = int(d)
lily = input()
j = 0
jump = 0
while True:
	find = 0
	for i in range(d, 0, -1):
		if i + j >= n:
			continue
		if lily[i + j] == '1':
			j = j + i
			jump += 1
			find = 1
			break
	if find == 0:
		print(-1)
		break
	if j == n - 1:
		print(jump)
		break


n = [int(s) for s in input().split()]
a = list(input())
m = 0
p = True
r = 0
while m != n[0] - 1 and p:
	o = True
	for i in range(n[1]):
		k = m + n[1] - i
		if k < n[0]:
			if a[k] == '1' and o:
				m = k
				r += 1
				o = False
	if o:
		print(-1)
		p = False
	if m == n[0] - 1:
		print(r)


(n, d) = map(int, input().split())
arr = list(map(int, list(input())))
arr = [d if i == 1 else 0 for i in arr]
jumps = [float('inf')] * n
jumps[0] = 0
for i in range(1, n):
	for j in range(0, i):
		if arr[j] + j >= i:
			jumps[i] = min(jumps[j] + 1, jumps[i])
if jumps[-1] != float('inf'):
	print(jumps[i])
else:
	print(-1)


import sys

def get_last_index(s, jumpLength):
	indexes = list()
	for i in range(len(s)):
		if s[i] == '1':
			indexes.append(i)
	ls = [j for j in indexes if j < jumpLength]
	return not ls and -1 or max(ls)

def min_number(jumpLength, s, count=0):
	if len(s) == 0:
		return count
	elif s == '1' * len(s) and jumpLength == 1:
		return len(s)
	else:
		i = get_last_index(s, jumpLength)
		return i == -1 and -1 or (jumpLength >= i and min_number(jumpLength, s[i + 1:], count + 1))
sys.setrecursionlimit(100000)
ls = [int(i) for i in input().split()]
s = input()
print(min_number(ls[1], s[1:]))


(n, m) = map(int, input().split())
s = input()
c = 0
t = m
i = 0
while i < len(s):
	if t != 0 and i + t in range(len(s)) and (s[i + t] == '1'):
		c = c + 1
		i = i + t
		t = m
		continue
	elif t != 0:
		t = t - 1
		continue
	else:
		break
	if i == len(s) - 1:
		break
if len(s) == 1:
	print(0)
	exit()
if c and i == len(s) - 1:
	print(c)
else:
	print(-1)


(n, d) = [int(i) for i in input().split()]
a = input()
dp = [1000000000.0] * n
dp[0] = 0
for i in range(1, n):
	if a[i] == '0':
		continue
	for j in range(1, d + 1):
		if i - j < 0:
			break
		dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[-1] if dp[-1] != 1000000000.0 else -1)


(n, d) = map(int, input().split())
s = list(input())
l = []
for i in range(n):
	if s[i] == '1':
		l.append(i)
count = 0
flag = 1
start = 0
i = 0
we = len(l)
while i < we - 1:
	if l[i + 1] - l[i] > d:
		flag = 0
		break
	else:
		t = i + 1
		while t < we and l[t] - l[i] <= d:
			t += 1
		count += 1
		i = t - 1
if flag == 0:
	print(-1)
else:
	print(count)


line = input()
pui = line.split()
n = int(pui[0])
d = int(pui[1])
st = input()
pos = 1
j = 0
while True:
	temp = False
	i = pos + d
	if i >= n:
		j = j + 1
		temp = True
		break
	while i != pos:
		if st[i - 1] == '1':
			pos = i
			temp = True
			j = j + 1
			break
		i = i - 1
	if temp is False:
		print('-1')
		quit()
print(j)


def calculate_hops(n, d, s):
	idx = 0
	end_idx = n - 1
	pointer = idx + d
	hop_count = 0
	while idx != end_idx:
		if pointer == idx:
			print('-1')
			return
		elif s[pointer] == '1':
			idx = pointer
			if end_idx - d >= pointer:
				pointer += d
			else:
				pointer = end_idx
			hop_count += 1
		else:
			pointer -= 1
	print(hop_count)
	return
params = [int(x) for x in input().split()]
(n, d) = (params[0], params[1])
s = input()
calculate_hops(n, d, s)


(n, d) = list(map(int, input().split()))
arr = input()
(i, count) = (0, 0)
while i < n - 1 and count < n:
	if arr[i] == '1':
		i += d
		count += 1
	else:
		i -= 1
print(-1 if count >= n else count)


x = [int(s) for s in input().split()]
(n, d) = (x[0] - 1, x[1])
s = [int(v) for v in list(input())]

def prijok(s=[], i=0, d=0, co=0, n=0):
	if i + d >= n:
		print(co + 1)
		return
	for j in range(d, 0, -1):
		if s[i + j] == 1:
			prijok(s, i + j, d, co + 1, n)
			return
	if s[i + 1] == 0:
		print(-1)
		return
(i, co) = (0, 0)
prijok(s, i, d, co, n)


(n, d) = map(int, input().split())
s = input()
i = 0
ans = 0
hasOne = True
while hasOne:
	hasOne = False
	a = min(i + d, n - 1)
	while a > i:
		if s[a] == '1':
			ans += 1
			i = a
			hasOne = True
			break
		if a - 1 == i:
			ans = -1
		a -= 1
print(ans)


(n, d) = map(int, input().split())
s = input()
ls = list(s)
i = 0
cnt = 0
while True:
	j = d
	if i + j >= len(ls):
		j = len(ls) - i - 1
	while j > 0:
		if ls[i + j] == '1':
			i += j
			cnt += 1
			break
		j -= 1
	else:
		cnt = -1
		break
	if i >= len(ls) - 1:
		break
print(cnt)


(n, d) = map(int, input().split())
s = input()
l = []
ans = 1
for i in range(n):
	if s[i] == '1':
		l.append(i + 1)

def foo(x):
	k = []
	c = l.index(x)
	for f in range(c + 1, len(l)):
		if l[f] - x <= d:
			k.append(l[f])
		else:
			break
	if len(k) == 0:
		return False
	else:
		return k[-1]
u = 0
while True:
	if u == 0:
		v = foo(l[0])
		u = v
	else:
		v = foo(u)
		u = v
	if v == False:
		ans = -1
		break
	elif v == l[-1]:
		break
	else:
		ans += 1
print(ans)


(n, d) = input().split()
(n, d) = (int(n), int(d))
str1 = input()
count = 0
i = 0
if '0' * d in str1:
	print(-1)
else:
	while i < n - 1:
		if str1[i] == '1':
			i += d
			count += 1
		else:
			i -= 1
	print(count)


import math
(N, D) = map(int, input().split())
S = input()
L = list()
L.append(0)
for i in range(1, N):
	if S[i] == '1':
		L.append(math.inf)
		for j in range(i - D, i + 1):
			if j >= 0:
				L[i] = min(L[i], L[j] + 1)
	else:
		L.append(math.inf)
if L[-1] != math.inf:
	print(L[-1])
else:
	print(-1)


(n, d) = [int(i) for i in input().split()]
s = input()
lagyha_now = 0
ans = 0
while lagyha_now < n - 1:
	jump = min(d, n - lagyha_now - 1)
	while s[lagyha_now + jump] != '1':
		jump -= 1
		if jump < 1:
			print(-1)
			quit()
	lagyha_now += jump
	ans += 1
print(ans)


(n, d) = map(int, input().split())
n += 1
count = 0
s = '1' + input()
pos = 1
while pos < n - 1 and count < n:
	if s[pos] == '1':
		count += 1
		pos += d
	else:
		pos -= 1
if count >= n:
	print(-1)
else:
	print(count)


def main():
	(n, d) = map(int, input().split(' '))
	l = list(input())
	c = {}
	c[1] = 0
	c[0] = int(1000000000.0)
	for i in range(len(l)):
		if l[i] == '0':
			c[i + 1] = int(1000000000.0)

	def f(x):
		nonlocal c, d, l
		if x in c:
			return c[x]
		ret = int(1000000000.0)
		if x > n or x < 0:
			c[n] = ret
			return ret
		if l[x - 1] == '0':
			return ret
		for i in range(1, d + 1):
			ret = min(ret, 1 + f(x - i))
		c[x] = ret
		return ret
	x = f(n)
	return x if x != int(1000000000.0) else -1
print(main())


(n, d) = [int(_) for _ in input().split()]
s = input()
ff = {n - 1: 0}

def f(k):
	global ff
	if not k in ff:
		www = []
		for i in range(k + 1, min(k + d + 1, n)):
			if s[i] == '1':
				www.append(f(i))
		if www:
			ff[k] = min(www) + 1
		else:
			ff[k] = 10000
	return ff[k]
rez = f(0)
if rez > 1000:
	rez = -1
print(rez)


(n, d) = map(int, input().split())
s = input()
nodes = [i for i in range(n) if s[i] == '1']
best = [None] * len(nodes)

def find_best(node_idx):
	if best[node_idx]:
		return best[node_idx]
	if node_idx == len(nodes) - 1:
		return 0
	if n - nodes[node_idx] <= d:
		return 1
	cases = [find_best(idx) for idx in range(node_idx + 1, len(nodes)) if nodes[idx] - nodes[node_idx] <= d]
	if cases:
		best[node_idx] = min(cases) + 1
		return best[node_idx]
	else:
		return float('inf')
res = find_best(0)
if res == float('inf'):
	print(-1)
else:
	print(res)


(n, k) = map(int, input().split())
s = input()
(i, j, ans) = (0, 0, 0)
while i != n - 1:
	flag = 0
	for j in range(min(n - 1, i + k), i, -1):
		if s[j] == '1':
			i = j
			flag = 1
			ans += 1
			break
	if flag == 0:
		exit(print('-1'))
print(ans)


[n, d] = list(map(int, input().split()))
s = list(map(int, list(input())))
f = True
i = n - 1
c = 0
while i > 0:
	k = i
	for j in range(i - d, i + 1):
		if s[j] == 1:
			c += 1
			i = j
			break
	if k == i:
		f = False
		break
if f:
	print(c)
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
i = 0
old_i = 0
count = 0
while True:
	old_i = i
	i += d
	count += 1
	i = min(i, n - 1)
	if i == n - 1:
		print(count)
		exit()
	else:
		while s[i] != '1':
			i -= 1
			if i == old_i:
				print(-1)
				exit()


R = lambda : map(int, input().split())
(n, d) = R()
a = list(map(int, input()))
res = [101] * n
res[0] = 0
for i in range(1, n):
	if a[i]:
		for j in range(max(0, i - d), i):
			if a[j] < 101:
				res[i] = min(res[i], res[j] + 1)
print(res[-1] if res[-1] < 101 else -1)


(n, d) = map(int, input().split())
s = list(map(int, input()))
dp = [1000 for i in range(n)]
dp[0] = 0
for i in range(1, n):
	if not s[i]:
		continue
	for j in range(1, min(i, d) + 1):
		if s[i - j]:
			dp[i] = min(dp[i], dp[i - j] + 1)
if dp[-1] < 1000:
	print(dp[-1])
else:
	print(-1)


nums = input().split()
n = int(nums[0])
d = int(nums[1])
Str = str(input())
min_jumps = 0
dp = []
for i in range(n):
	dp.append(float('inf'))
dp[0] = 0
dp[1] = 1
for i in range(2, n):
	for j in range(1, d + 1):
		if Str[i] == '1':
			if dp[i - j] + 1 < dp[i]:
				dp[i] = dp[i - j] + 1
		else:
			break
prev_indx = 0
for i in range(1, len(Str)):
	if Str[i] == '1':
		if i - prev_indx > d:
			min_jumps = -1
			break
		prev_indx = i
		min_jumps = dp[i]
print(min_jumps)


(a, b) = map(int, input().split())
c = input()
ar = [101] * a
ar[a - 1] = 0
cm = [0] * a
for i in range(a):
	if c[i] == '1':
		cm[i] = 1
for i in range(a - 1, -1, -1):
	if cm[i] == 1:
		for ii in range(i - 1, i - b - 1, -1):
			if cm[ii] == 1:
				ar[ii] = min(ar[i] + 1, ar[ii])
if ar[0] == 101:
	print(-1)
else:
	print(ar[0])


(n, d) = map(int, input().split())
s = list(map(int, input()))
a = [-1] * n
a[0] = 0
for i in range(1, n):
	if not s[i]:
		continue
	min_val = -1
	for j in range(1, d + 1):
		k = i - j
		if k < 0:
			break
		if a[k] < 0:
			continue
		if min_val < 0 or a[k] < min_val:
			min_val = a[k]
	if min_val >= 0:
		a[i] = min_val + 1
print(a[n - 1])


(n, d) = map(int, input().split())
a = input()
x = 0
r = 0
while x != n - 1:
	y = a[:x + d + 1].rfind('1')
	if y == x:
		r = -1
		break
	else:
		x = y
	r += 1
print(r)


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
PI = float('inf')
for _ in range(1):
	(n, k) = lst()
	s = input()
	dp = [PI] * n
	dp[0] = 0
	for i in range(1, n):
		if s[i] == '0':
			continue
		for j in range(i - 1, i - k - 1, -1):
			dp[i] = min(dp[i], dp[j] + 1)
	print(dp[n - 1] if dp[n - 1] != PI else -1)


(n, d) = map(int, input().split())
s = list(input())
lili = list()
for i in range(len(s)):
	if s[i] == '1':
		lili.append(i + 1)
jmp = 0
lili.reverse()
curr_sum = 0
flag = 0
diff = 0
for i in range(len(lili) - 1):
	if lili[i] - lili[i + 1] > d:
		print(-1)
		flag = 1
		break
	else:
		diff = lili[i] - lili[i + 1]
		if curr_sum + diff > d:
			jmp += 1
			curr_sum = diff
		else:
			curr_sum += diff
if flag == 0:
	if curr_sum <= d:
		jmp += 1
	print(jmp)


import math
(n, d) = map(int, input().split())
s = input()
f = len(s)
l = []
for i in range(f):
	l.append(int(s[i]))
p = l.copy()
for i in range(f):
	if l[i] == 1:
		p[i] = i
	else:
		p[i] = p[i - 1]
k = 0
i = 0
c = 0
m = 0
while i != n - 1:
	if i + d < f - 1:
		m = p[i + d]
	else:
		m = f - 1
	if m == i:
		k = 1
		print(-1)
		break
	else:
		i = m
		c += 1
if k != 1:
	print(c)


(n, d) = map(int, input().split())
a = [int(i) for i in input()]
ans = [float('inf') for i in range(n)]
ans[0] = 0
for i in range(n):
	for j in range(i + 1, i + 1 + d):
		if j < n:
			if a[j] == 1:
				ans[j] = min(ans[j], ans[i] + 1)
if ans[n - 1] < float('inf'):
	print(ans[n - 1])
else:
	print(-1)


(n, d) = map(int, input().split())
x = input()
cnt = 0
if x.count(d * '0') > 0:
	print(-1)
else:
	(left_pointer, right_pointer) = (0, 0)
	for i in range(1, n):
		if x[i] == '1':
			if i - left_pointer < d:
				right_pointer = i
				if i == n - 1:
					cnt += 1
			else:
				(left_pointer, right_pointer) = (i, i)
				cnt += 1
		elif i - left_pointer == d:
			left_pointer = right_pointer
			cnt += 1
	print(cnt)


(nPads, jmp) = [int(x) for x in input().split()]
pads = input()
i = 1
nJumps = 0
while i < nPads:
	if i + jmp >= nPads:
		nJumps += 1
		break
	canJump = False
	for j in range(jmp, 0, -1):
		if pads[i + j - 1] == '1':
			canJump = True
			nJumps += 1
			i += j
			break
	if not canJump:
		nJumps = -1
		i = 200
print(nJumps)


(n, d) = input().split(' ')
n = int(n) - 1
d = int(d)
s = input()
curr_index = 0
jump_counter = 0
while curr_index < n:
	try:
		curr_index = s.rindex('1', curr_index + 1, curr_index + 1 + d)
		jump_counter += 1
	except ValueError:
		print(-1)
		break
	if curr_index >= n:
		print(jump_counter)


(n, d) = map(int, input().split())
s = input()
count = 0
i = 0
while i != n - 1:
	f1 = False
	j = min(i + d, n - 1)
	while j > i:
		if s[j] == '1':
			f1 = True
			break
		j -= 1
	if f1:
		i = j
		count += 1
	else:
		break
if i == n - 1:
	print(count)
else:
	print(-1)


(n, d) = map(int, input().split(' '))
s = input()
y = []
for i in s:
	y.append(i)
i = count = 0
x = d
while x > 0 and i < n - d:
	if y[i + x] == '1':
		count += 1
		i += x
		x = d + 1
	x -= 1
if x == 0:
	print(-1)
elif i != n - 1:
	print(count + 1)
else:
	print(count)


def solution(n, d, L):
	current_pos = 0
	jumps = 0
	while current_pos < n - 1:
		longest_jump = min(d, n - 1 - current_pos)
		while L[current_pos + longest_jump] != '1' and longest_jump >= 0:
			longest_jump -= 1
		if longest_jump == 0:
			return -1
		current_pos += longest_jump
		jumps += 1
	return jumps
(n, k) = map(int, input().split())
L = input()
print(solution(n, k, L))


(n, d) = map(int, input().split())
s = input()
INF = float('inf')
dp = [INF] * n
dp[0] = 0
for i in range(n):
	for j in range(d + 1):
		if i + j < n and s[i + j] == '1':
			dp[i + j] = min(dp[i + j], dp[i] + 1)
if dp[n - 1] == INF:
	print(-1)
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
A = input()
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
	for j in range(max(i - d, 0), i):
		if A[i] == '1':
			dp[i] = min(dp[i], 1 + dp[j])
print(dp[-1] if dp[-1] != float('inf') else -1)


inp = lambda : map(int, input().rstrip().split())
(n, d) = inp()
s = input()
maxm = 0
count = 0
for i in s:
	if i == '0':
		count += 1
	else:
		maxm = max(maxm, count)
		count = 0
if maxm >= d:
	print(-1)
	exit()
t = 0
steps = 0
while t < n - 1:
	for i in range(min(t + d, n - 1), t, -1):
		if s[i] != '0':
			steps += 1
			t = i
			break
print(steps)


(n, d) = map(int, input().split())
s = input()
p = 0
ans = 0
while p < n - 1:
	np = p
	for i in range(1, min(d + 1, n - p)):
		if s[p + i] == '1':
			np = p + i
	if np == p:
		break
	p = np
	ans += 1
if p == n - 1:
	print(ans)
else:
	print(-1)


(n, m) = map(int, input().split())
a = str(input())
st = 0
sp = 0
while st < n - 1:
	i = min(st + m, n - 1)
	while a[i] != '1':
		i -= 1
	if i == st:
		print(-1)
		exit()
	st = i
	il = st
	sp += 1
print(sp)


(n, d) = map(int, input().split())
s = list(input().strip())
jumps = 0
i = 0
while i < n - 1:
	j = min(i + d, n - 1)
	while s[j] != '1':
		j -= 1
	jumps += 1
	if i == j:
		print(-1)
		import sys
		sys.exit(0)
	i = j
print(jumps)


import sys
Lines = []
for Line in sys.stdin:
	Lines.append(Line.rstrip('\n'))
(n, d) = list(map(int, Lines[0].split(' ')))
del Lines[0]
s = list(map(int, [i for i in Lines[0]]))
memo = [-1 for j in range(n)]
dp = [0 for j in range(n)]

def min_jumps2(s, d, i):
	if i == 0:
		return 0
	c = []
	for j in range(1, d + 1):
		if i - j >= 0 and s[i - j] == 1:
			c += [1 + min_jumps(s, d, i - j)]
	if c == []:
		print(-1)
		exit(0)
	return min(c)

def min_jumps0(s, d, i):
	if i == 0:
		return 0
	c = []
	for j in range(1, d + 1):
		if i - j >= 0 and s[i - j] == 1:
			if memo[i - j] != -1:
				print(i, j)
				t = memo[i - j]
			else:
				t = min_jumps(s, d, i - j)
				memo[i - j] = t
			c += [1 + t]
	if c == []:
		print(-1)
		exit(0)
	return min(c)

def min_jumps(s, d, i):
	for i in range(1, n):
		c = []
		for j in range(1, d + 1):
			if i - j >= 0 and s[i - j] == 1:
				c += [1 + dp[i - j]]
		if c == []:
			return -1
		else:
			dp[i] = min(c)
	return dp[n - 1]
print(min_jumps(s, d, n - 1))


def jump(n, d, s):
	string = ''
	for x in range(d):
		string += '0'
	for i in range(len(s) - d):
		if s[i:i + d] == string:
			return -1
	count = 0
	dist = 1
	a = 0
	r = 1
	while dist < len(s):
		if d + a < len(s):
			if int(s[d + a]) == 1:
				dist += d
				count += 1
				a += d
			else:
				while d - r > 0:
					if int(s[d + a - r]) == 1:
						dist += d - r
						count += 1
						a += d - r
						r = 1
						break
					else:
						r += 1
		else:
			a -= 1
	return count

def __starting_point():
	[n, d] = [int(i) for i in input().split(' ')]
	s = input()
	print(jump(n, d, s))
__starting_point()


(n, m) = map(int, input().split())
k = input()
p = 0
c = 0
while p != n - 1:
	i = p
	h = m
	while h != 0:
		if i + h < n:
			if k[i + h] == '1':
				p = i + h
				c += 1
				break
		h -= 1
	if i - p == 0 and p != n - 1:
		print(-1)
		break
	elif p == n - 1:
		print(c)


(n, d) = map(int, input().split())
s = input()
s = list(s)
answ = 0
while s:
	del s[0]
	if not s:
		break
	for i in reversed(range(d)):
		try:
			leng = s.index('1', i, d)
			answ += 1
			break
		except ValueError:
			pass
	else:
		answ = -1
		break
	for i in range(1, leng + 1):
		del s[0]
print(answ)


(n, k) = map(int, input().split())
s = input()
if s[0] != '1' or s[-1] != '1':
	print(-1)
else:
	cnt = 0
	i = 0
	f = 1
	while i != n - 1:
		ind = -1
		for j in range(i + 1, min(n, i + 1 + k)):
			if s[j] == '1':
				ind = j
		if ind == -1:
			print(-1)
			f = 0
			break
		i = ind
		cnt += 1
	if f:
		print(cnt)


def g():
	arrlen = list(map(int, input().split()))
	arr = list(map(int, input()))
	p1 = 0
	p2 = 0
	leaps = 0
	while True:
		if p1 == arrlen[0] - 1:
			break
		else:
			p2 = min(p1 + arrlen[1], arrlen[0] - 1)
			while True:
				if p1 == p2:
					print('-1')
					return
				elif arr[p2] == 1:
					p1 = p2
					leaps += 1
					break
				else:
					p2 -= 1
	print(leaps)
g()


(n, d) = map(int, input().split())
s = input()
if max(list((len(i) for i in s.split('1')))) >= d:
	print(-1)
else:
	ans = 0
	i = 0
	while i < n - 1:
		for j in range(min(n - 1, i + d), i, -1):
			if s[j] == '1':
				ans += 1
				i = j
				break
	print(ans)


(n, d) = [int(x) for x in input().split()]
s = input()
position = 0
saut = 0
boucle = True
while boucle and position != n - 1:
	boucle = False
	for x in range(d, 0, -1):
		if position + x > n - 1:
			continue
		if s[position + x] == '1':
			position += x
			saut += 1
			boucle = True
			break
if position == n - 1:
	print(saut)
else:
	print(-1)


(n, d) = map(int, input().split())
string = str(input())
dp = [0] * n
last_i = -1
flag = 0
if string[0] == '1' and string[-1] == '1':
	last_i = 0
else:
	flag = 1
if flag == 0:
	for i in range(1, n):
		if string[i] == '0':
			if last_i > i - d:
				dp[i] = dp[last_i] + 1
			else:
				flag = 1
				break
		else:
			if i - d <= 0:
				dp[i] = 1
			elif string[i - d] == '0':
				min_ = min(dp[i - d:i])
				dp[i] = min_ + 1
			else:
				dp[i] = dp[i - d] + 1
			last_i = i
if flag == 0:
	print(dp[n - 1])
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
lst = {i: 0 for i in range(n)}
for i in range(1, d + 1):
	if s[i] == '1':
		lst[i] = 1
for i in range(d + 1, n):
	if s[i] == '1':
		mi = 1000000
		for j in range(i - d, i):
			a = lst[j]
			if a > 0:
				if a < mi:
					mi = a
		lst[i] = mi + 1
res = lst[n - 1]
if res == 1000001:
	print(-1)
else:
	print(res)


import sys
sys.setrecursionlimit(2000)
inf = float('inf')
mod = 1000000007

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

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

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

def recurse():
	for i in range(2, n + 1):
		if arr[i - 1] == '1':
			for j in range(d + 1):
				if i - j >= 1:
					dp[i] = min(dp[i], 1 + dp[i - j])
	return dp[n] if dp[n] != inf else -1
(n, d) = get_ints()
arr = input()
dp = [inf] * (n + 1)
dp[1] = 0
print(recurse())


(n, d) = map(int, input().split())
s = str(input())
s += '0' * 101
res = 0
now = 0
p = 0
while now != n - 1:
	for i in range(d, 0, -1):
		if s[now + i] == '1':
			now += i
			break
	res += 1
	p += 1
	if p == 1000:
		print(-1)
		break
else:
	print(res)


z = input
mod = 10 ** 9 + 7
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
(a, b) = map(int, z().split())
s = z()
s1 = s.split('1')
c = 0
for i in s1:
	if len(i) >= b:
		print(-1)
		exit(0)
k = 0
for _ in range(a):
	for j in range(k + b, k, -1):
		try:
			if s[j] == '1':
				c += 1
				k = j
				break
		except:
			pass
print(c)


(n, d) = map(int, input().split())
lily = list(map(int, input()))

def ans(lily, d):
	dp = [0]
	for i in range(1, d + 1):
		dp.append(1000 if lily[i] == 0 else lily[i])
	for i in range(d + 1, n):
		if lily[i] == 0:
			dp.append(1000)
		else:
			l = min(dp[len(dp) - 1:len(dp) - d - 1:-1])
			if l == 1000:
				dp.append(1000)
			else:
				dp.append(l + 1)
	return -1 if dp[-1] == 1000 else dp[-1]
print(ans(lily, d))


(n, d) = map(int, input().split())
ch = input()
(stepCount, frog, blocked) = (0, 0, False)
while frog < n - 1 and (not blocked):
	i = min(d + frog, n - 1)
	stepFound = False
	while i > frog and (not stepFound):
		if ch[i] == '1':
			stepFound = True
			frog = i
			stepCount += 1
		else:
			i -= 1
	if stepFound == False:
		blocked = True
		stepCount = -1
print(stepCount)


(n, d) = [int(i) for i in input().split()]
a = input()
inf = 1000
dp = [inf] * n
dp[0] = 0
for i in range(n - 1):
	for j in range(1, min(n - i, d + 1)):
		if a[i + j] == '1':
			dp[i + j] = min(dp[i + j], dp[i] + 1)
print(dp[n - 1] if dp[n - 1] != inf else -1)


(n, d) = map(int, input().split())
path = input()
dp = [10 ** 5] * n
dp[0] = 0
for i in range(n):
	if path[i] == '1':
		for j in range(i + 1, min(n, i + d + 1)):
			if path[j] == '1':
				dp[j] = min(dp[j], dp[i] + 1)
if dp[n - 1] > 10 ** 4:
	print(-1)
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
s = '1' + input()
x = 1
k = 1
while x + d < n:
	i = d
	while s[i + x] == '0':
		i -= 1
		if i == 0:
			k = -1
			break
	else:
		x += i
		k += 1
		continue
	break
print(k)


import math, sys, time, random
(n, d) = map(int, input().split())
a = input()
i = 0
jump = 0
while i < n - 1:
	i += d
	j = i
	while j < n and a[j] != '1':
		j -= 1
	jump += 1
	i = j
	if jump > a.count('1'):
		print(-1)
		sys.exit()
print(jump)


from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
(n, d) = iia()
s = is1()
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
	if s[i] == '1':
		for j in range(max(0, i - d), i):
			dp[i] = min(dp[j] + 1, dp[i])
if dp[-1] == float('inf'):
	print(-1)
else:
	print(dp[-1])


(n, d) = map(int, input().split())
A = input()

def solve():
	if A[-1] == '0':
		return -1
	currReachable = maxReachable = n - 1
	ans = 1
	for i in range(n - 2, -1, -1):
		if A[i] == '1':
			if i + d >= maxReachable:
				currReachable = i
			elif i + d < maxReachable and currReachable - d <= i:
				ans += 1
				maxReachable = currReachable
				currReachable = i
			else:
				return -1
	return ans if currReachable == 0 else -1
print(solve())


(n, d) = map(int, input().split())
a = [int(i) for i in input()]
k = 0
f = 1
ind = 0
while f:
	g = 0
	for i in range(ind + 1, ind + d + 1):
		if i >= len(a):
			break
		if a[i] == 1:
			g = 1
			ind = i
	k += 1
	if g == 0 or ind == n - 1:
		break
if ind == n - 1:
	print(k)
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
cords = []
jumps = 0
frogcord = 0
end = False
ez = False
for i in range(len(s)):
	if s[i] == '1':
		cords.append(i + 1)
if n == 2:
	print(1)
else:
	for i in range(len(cords)):
		for j in range(1, len(cords)):
			if cords[j] - cords[frogcord] > d:
				if cords[j - 1] - cords[frogcord] <= d:
					jumps += 1
					frogcord = j - 1
			if n - cords[frogcord] <= d:
				jumps += 1
				frogcord = len(cords) - 1
				end = True
				ez = True
				break
		if end:
			break
	if frogcord == 0 and (not ez):
		jumps = -1
	if jumps >= n or cords[frogcord] != n:
		jumps = -1
	print(jumps)


(n, d) = map(int, input().split(' '))
l = list(input())
pos = 1
a = 1
nb = 0
while (pos != 0) & (a < n):
	l1 = l[a:a + d]
	k = 0
	pos = 0
	for i in l1:
		k = k + 1
		if int(i) == 1:
			pos = k
	nb = nb + 1
	a = a + pos
if pos != 0:
	print(nb)
else:
	print(-1)


(n, m) = map(int, input().split())
a = list(input())
i = 0
ans = 0
while i + m <= n - 1:
	for j in range(0, m):
		if a[m + i - j] == '1':
			i = m + i - j
			ans += 1
			break
	else:
		print(-1)
		exit()
if i != n - 1:
	print(ans + 1)
else:
	print(ans)


def dfs(poc, duz):
	if poc >= n - 1:
		return duz
	if bio[poc] == 1:
		return -1
	bio[poc] = 1
	if s[poc] == '0':
		return -1
	for i in range(d, 0, -1):
		temp = dfs(poc + i, duz + 1)
		if temp >= 0:
			return temp
	return -1
(n, d) = map(int, input().split())
s = input()
bio = [0 for i in range(n + 1)]
print(dfs(0, 0))


def solve(n, d, s):
	dp = [99999] * n
	dp[0] = 0
	for i in range(n - 1):
		if s[i] == '0':
			continue
		for j in range(i + 1, i + d + 1):
			if j > n - 1:
				break
			if s[j] == '0':
				dp[j] = 0
				continue
			elif s[j] == '1':
				dp[j] = min(dp[i] + 1, dp[j])
	if dp[n - 1] == 99999:
		dp[n - 1] = -1
	print(dp[n - 1])
(n, d) = map(int, input().split())
ar = list(input())
solve(n, d, ar)


def solve(field, D):
	valid_idxs = [i for (i, c) in enumerate(field) if c == '1']
	path = [float('inf')] * len(field)
	path[0] = 0
	i = 0
	while i < len(path):
		for idx in valid_idxs:
			if idx <= i:
				continue
			elif idx > i and idx <= i + D:
				path[idx] = min(path[idx], path[i] + 1)
			else:
				break
		i += 1
	return path[-1] if path[-1] != float('inf') else -1
(N, D) = map(int, input().split())
field = input()
print(solve(field, D))


(n, d) = map(int, input().split())
a = input()
c = 0
i = 0

def f(x, a):
	if x < len(a) and a[x] == '1':
		return 1
while i < len(a):
	if i + 1 == n:
		break
	for j in range(d, 0, -1):
		if f(i + j, a):
			i = i + j
			c += 1
			break
	else:
		c = -1
		break
print(c)


def main():
	(n, d) = map(int, input().split())
	l = list(map(int, list(input())))
	m = [n] * n
	m[0] = 0
	for i in range(n):
		if l[i]:
			for j in range(max(0, i - d), i):
				if m[j] < m[i]:
					m[i] = m[j] + 1
	o = m[n - 1]
	if o == n:
		print(-1)
	else:
		print(o)
main()


s1 = input()
s1 = s1.split()
n = int(s1[0])
d = int(s1[1])
s = input()
count = 0
pos = 1
dk = d
res = True
while pos != n:
	if dk == 0:
		res = False
		break
	if pos + dk <= n and s[pos + dk - 1] == '1':
		if dk == 0:
			res = False
			break
		pos += dk
		count += 1
		dk = d
	else:
		dk -= 1
if res:
	print(count)
else:
	print(-1)


(m, n) = [int(x) for x in input().split(' ')]
raw = list(input())
p = 0
cnt = 1
prt = 0
while p < m - n - 1:
	for j in range(n):
		key = 0
		if raw[p + n - j] == '1':
			p = p + n - j
			cnt += 1
			key = 1
			break
		else:
			pass
	if key == 0:
		prt = 1
		break
if prt == 1:
	print(-1)
else:
	print(cnt)


(a, b) = map(int, input().split())
z = input()
(i, q) = (0, 0)
while i < a - 1:
	x = z[i + 1:i + b + 1]
	w = x[::-1]
	if '1' in w:
		q += 1
		i += b - w.index('1')
	else:
		q = -1
		break
print(q)


(n, k) = map(int, input().split())
s = str(input())
c = 0
i = 1
while i < n:
	if s[i:min(i + k, n)].count('1') == 0:
		c = -1
		break
	else:
		i = k - s[min(i + k - 1, n - 1):i - 1:-1].index('1') + i
		c += 1
print(c)


(n, d) = map(int, input().split())
s = input()
i = 0
count = 0
possible = True
while i < n - 1:
	for c in range(min(i + d, n - 1), i, -1):
		if s[c] == '1':
			count += 1
			i = c
			break
	else:
		possible = False
		break
if possible:
	print(count)
else:
	print(-1)


(n, d) = map(int, input().split(' '))
s = input()
mincnt = 0
k = 0
ki = 0
km = 0
L = len(s)
for i in range(1, L):
	if s[i] == '1':
		k = i
	if i - km >= d or i == L - 1:
		if k == km:
			mincnt = -1
			break
		km = k
		mincnt += 1
print(mincnt)


(n, d) = list(map(int, input().split(' ')))
s = input()
location = 0
jump_counter = 0
i = 0
while i < len(s):
	i += d
	if i >= len(s) - 1:
		jump_counter += 1
		print(jump_counter)
		exit()
	while not int(s[i]) and i > location:
		i -= 1
	if i == location:
		print('-1')
		exit()
	else:
		location = i
		jump_counter += 1
print(jump_counter)


(n, d) = map(int, input().split())
n -= 1
s = input()
ans = 0
while n != 0:
	ans += 1
	test = False
	for j in range(d):
		if n - (d - j) >= 0 and s[n - (d - j)] == '1':
			n -= d - j
			test = True
			break
	if not test:
		print(-1)
		exit(0)
print(ans)


nd = list(map(int, input().split()))
s = str(input())
temp = 0
steps = 0
while temp != nd[0] - 1:
	accept = 1
	for i in range(min(temp + nd[1], nd[0] - 1), temp, -1):
		if s[i] == '1':
			temp = i
			accept = 0
			break
	if accept == 1:
		break
	steps += 1
if accept == 1:
	print(-1)
else:
	print(steps)


(n, d) = map(int, input().split())
a = list(map(int, input()))
ans = 0
di = d
i = 0
while di > 0 and i != n - 1:
	if i + di >= n:
		di = n - 1
		i = 0
	if a[i + di] == 1:
		ans += 1
		i = i + di
		di = d
	else:
		di -= 1
	if di == 0:
		print(-1)
		exit()
print(ans)


(n, d) = map(int, input().split())
s = input()
ones = []
for i in range(n):
	if s[i] == '1':
		ones.append(i)
flag = False
for i in range(len(ones) - 1):
	if ones[i + 1] - ones[i] > d:
		flag = True
		break
if flag == True:
	print(-1)
else:
	i = 0
	j = 1
	cnt = 0
	while j < len(ones):
		if ones[j] > ones[i] + d:
			i = j - 1
			cnt = cnt + 1
		else:
			j = j + 1
	print(cnt + 1)


(total_dist, max_jump) = list(map(int, input().split()))
s = input()
dp = [101] * total_dist
dp[0] = 0
for i in range(total_dist):
	if s[i] == '1':
		for j in range(max_jump + 1):
			if i + j < total_dist and s[i + j] == '1':
				dp[i + j] = min(dp[i + j], dp[i] + 1)
if dp[total_dist - 1] == 101:
	print(-1)
else:
	print(dp[total_dist - 1])


from queue import Queue
BigNum = 10 ** 10
(n, d) = map(int, input().split(' '))
gs = [False] + [c == '1' for c in input()]
ds = [BigNum] * len(gs)
q = Queue()
q.put((1, 0))
while not q.empty():
	(v, dist) = q.get()
	if not gs[v]:
		continue
	if ds[v] < BigNum:
		continue
	ds[v] = dist
	for dx in range(-d, d + 1):
		if 1 <= v + dx <= n:
			q.put((v + dx, dist + 1))
print(-1 if ds[n] == BigNum else ds[n])


def main():
	(n, d) = map(int, input().split(' '))
	ip = input()
	if d >= n:
		print('1\n')
		exit()
	i = 1
	curr = 0
	prev = 0
	jumps = 0
	while curr < len(ip) and i < len(ip):
		if ip[i] == '1':
			if i - curr > d and prev == 0:
				break
			elif i - curr > d and prev != 0:
				if i - prev > d:
					jumps = 0
					break
				curr = prev
				i = curr
				jumps += 1
			elif i == len(ip) - 1:
				jumps += 1
				break
			prev = i
		i += 1
	if jumps == 0:
		print('-1')
	else:
		print(jumps)
main()


(n, d) = map(int, input().split())
string = input()

def f(arr, num):
	if arr == '1':
		print(num)
		quit()
	for i in range(d, 0, -1):
		if i > len(arr) - 1:
			continue
		if arr[i] != '0':
			f(arr[i:], num + 1)
			break
f(string, 0)
print('-1')


(X, Lines, index, Counter) = (list(map(int, input().split())), input(), 0, 0)
if '0' * X[1] in Lines:
	print(-1)
	exit()
while index < X[0] - 1:
	Counter += 1
	index += Lines[index:index + X[1] + 1].rindex('1')
print(Counter)


from sys import stdin
(n, d) = map(int, stdin.readline().split())
path = stdin.readline()
pos = 0
ans = 0
while pos + d < n - 1:
	flag = True
	for i in range(pos + d, pos, -1):
		if path[i] == '1':
			pos = i
			ans += 1
			flag = False
			break
	if flag:
		ans = -2
		break
print(ans + 1)


class Graph:

	def __init__(self, size):
		self.size = size
		self.adj_list = {}
		for i in range(size):
			self.adj_list[i] = []

	def add_edge(self, src, des):
		self.adj_list[src].append(des)

	def BFS(self, src):
		d2s = [-1 for i in range(self.size)]
		visited = [False for i in range(self.size)]
		d2s[src] = 0
		visited[src] = True
		queue = [src]
		while len(queue) != 0:
			u = queue.pop(0)
			for node in self.adj_list[u]:
				if not visited[node]:
					visited[node] = True
					d2s[node] = d2s[u] + 1
					queue.append(node)
		return d2s

def main():
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	g = Graph(n)
	t = input()
	for j in range(len(t)):
		if t[j] == '1':
			for k in range(j + 1, j + d + 1):
				try:
					if t[k] == '1':
						g.add_edge(j, k)
				except IndexError:
					continue
	print(g.BFS(0)[-1])
main()


(n, d) = list(map(int, input().split()))
s = input()
i = n - 1
jmps = 1
fail = False
while True:
	x = max(i - d, 0)
	if x == 0:
		print(jmps)
		break
	ii = s.find('1', x, i)
	if ii == -1:
		print(-1)
		break
	i = ii
	jmps += 1


import sys, os.path
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
	sys.stdout = open('out.txt', 'w')
(n, x) = map(int, input().split())
s = input()
i = 0
ans = 0
no_ans = False
while i < n:
	p = i
	ans += 1
	i += x
	if i >= n - 1:
		break
	if s[i] != '1':
		while s[i] != '1':
			i -= 1
			if i <= p:
				no_ans = 1
				break
	if no_ans:
		break
if no_ans:
	print(-1)
else:
	print(ans)


(n, d) = map(int, input().split())
pole = input()
pozice = 0
a = 0
while pozice < n - 1:
	q = 0
	for i in range(d):
		if pozice + d - i < n:
			if pole[pozice + d - i] == '1':
				pozice = pozice + d - i
				q = 1
				a += 1
				break
	if q == 0:
		print(-1)
		break
if pozice >= n - 1:
	print(a)


(n, d) = map(lambda x: int(x), input().split())
road = input()
list = [int(x) for x in road]
step = d
num = 0
w = 0
t = False
while step > 0:
	if num + step >= n - 1:
		print(w + 1)
		t = True
		break
	elif list[num + step] == 0:
		step -= 1
	else:
		num += step
		step = d
		w += 1
if t == False:
	print(-1)


(n, d) = map(int, input().split())
a = input()
c = 0
i = 0
notreached = True
while notreached:
	ss = a[i + 1:i + d + 1]
	flag = True
	for j in range(len(ss) - 1, -1, -1):
		if ss[j] == '1':
			i += j + 1
			c += 1
			flag = False
			break
	if i == n - 1:
		notreached = False
	if flag:
		print('-1')
		break
if i == n - 1:
	print(c)


nd = input().split()
n = int(nd[0])
d = int(nd[1])
s = input()
(c, i) = (0, 0)
k = 0
while i != len(s) - 1:
	p = i + d
	if p > len(s) - 1:
		p = len(s) - 1
	for j in range(p, i, -1):
		if s[j] == '1':
			c += 1
			i = j
			break
	else:
		k = 1
		break
if k == 1:
	print(-1)
else:
	print(c)


class Problem:

	def __init__(self):
		(self.n, self.d) = map(int, input().split())
		self.s = input()
		self.counter = 0
		self.victory = False

	def solve(self, n):
		if n == self.n - 1:
			self.victory = True
			return
		break_point = -1
		self.counter += 1
		if n + self.d <= self.n - 1:
			for i in range(n + self.d, n, -1):
				if self.s[i] == '1':
					break_point = i
					break
		else:
			for i in range(self.n - 1, n, -1):
				if self.s[i] == '1':
					break_point = i
					break
		if break_point >= 0:
			self.solve(break_point)
		else:
			return

	def output(self):
		self.solve(0)
		if self.victory:
			print(self.counter)
		else:
			print('-1')
problem = Problem()
problem.output()


(n, d) = map(int, input().split())
s = input()
t = 0
ok = True
l = 1
while l < n and ok:
	k = l + d
	if k > n:
		k = n
	while s[k - 1] == '0':
		k -= 1
	if k == l:
		ok = False
		break
	l = k
	t += 1
if not ok:
	print(-1)
else:
	print(t)


(n, d) = map(int, input().split())
s = input()

def cal(n, d, s):
	if s[0] == '0' or s[-1] == '0':
		return -1
	st = 0
	out = 0
	temp = 0
	while st < n:
		for i in range(st + 1, min(n, st + d + 1)):
			if s[i] == '1':
				temp = i
		if temp == st:
			return -1
		st = temp
		out += 1
		if st == n - 1:
			return out
print(cal(n, d, s))


(n, d) = map(int, input().split())
st = input()
dp = [101 for i in range(n)]
dp[0] = 0
for i in range(1, n):
	if st[i] == '1':
		for j in range(i - 1, -1, -1):
			if j < i - d:
				break
			elif st[j] == '1' and dp[i] > dp[j] + 1:
				dp[i] = dp[j] + 1
if dp[n - 1] == 101:
	print(-1)
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
s = input()
ans = [1000 for i in range(1000)]
ans[0] = 0
for i in range(n):
	for j in range(i + 1, i + d + 1):
		if i >= n or s[i] != '1':
			continue
		ans[j] = min(ans[i] + 1, ans[j])
if ans[n - 1] == 1000:
	print(-1)
else:
	print(ans[n - 1])


import sys
(n, d) = [int(i) for i in input().split()]
s = input()
dp = [sys.maxsize] * (n + 1)
for i in range(n - 1):
	for j in range(i + 1, i + d + 1):
		if i == 0 and s[i] == '1' and (s[j] == '1'):
			dp[j] = min(dp[j], 1)
		if j < n:
			if s[i] == '1' and s[j] == '1':
				dp[j] = min(dp[j], dp[i] + 1)
if dp[n - 1] == sys.maxsize:
	print(-1)
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
l = input()
ans = 0
i = 0
p = -1
while i < n - 1:
	flag = 0
	for j in range(i + 1, min(i + d + 1, n)):
		if l[j] == '1':
			p = j
			flag = 1
	if flag == 1:
		ans += 1
		i = p
	else:
		break
if flag == 1:
	print(ans)
else:
	print(-1)


import collections
(n, d) = map(int, input().split())
str = input()
queue = collections.deque()
queue.append((0, 0))
answ = -1
while len(queue) > 0:
	curr = queue.popleft()
	index = curr[0]
	sz = curr[1]
	if index >= n:
		continue
	if index == n - 1:
		answ = sz
		break
	ch = str[index]
	if ch == '0':
		for i in range(index + d, index, -1):
			if i >= n:
				continue
			else:
				queue.append((i, sz + 1))
				break
	else:
		for i in range(index + d, index, -1):
			if i >= n:
				continue
			if str[i] == '1':
				queue.append((i, sz + 1))
				break
print(answ)


(n, d) = map(int, input().split())
s = input()

def jump(start):
	jumplen = 0
	for i in reversed(range(1, d + 1)):
		if start + i > len(s) - 1:
			if s[-1] == '1':
				jumplen = len(s) - start - 1
			else:
				jumplen = 0
		elif s[start + i] == '1':
			jumplen = i
			break
		else:
			pass
	return jumplen
flag = True
count = 0
st = 0
while flag:
	if st == len(s) - 1:
		flag = False
	else:
		pl = jump(st)
		if pl == 0:
			flag = False
			count = -1
		else:
			st = st + pl
			count += 1
print(count)


from sys import stdin, stdout
from collections import deque
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
PI = float('inf')
for _ in range(1):
	(n, k) = lst()
	s = input()
	q = deque()
	dp = [PI] * n
	dp[0] = 0
	q.append(0)
	for i in range(1, n):
		while q and i - q[0] > k:
			q.popleft()
		if s[i] == '1' and q:
			dp[i] = dp[q[0]] + 1
		while q and dp[q[-1]] > dp[i]:
			q.pop()
		if dp[i] != PI:
			q.append(i)
	print(dp[n - 1] if dp[n - 1] != PI else -1)


(n, d) = map(int, input().split())
string = input()
arr = []
for i in range(n):
	arr.append(int(string[i]))
curr = 0
flag = 0
count = 0
while curr != n - 1:
	nex = curr
	for i in range(1, d + 1):
		if curr + i < n and arr[curr + i] == 1:
			nex = curr + i
	if curr == nex:
		flag = 1
		print(-1)
		break
	curr = nex
	count += 1
if flag == 0:
	print(count)


(a, b) = [int(i) for i in input().split()]
s = list(str(input()))
s = ['0'] + s + b * ['0']
current = 1
result = 0
while current < a:
	can = 0
	for i in range(b, 0, -1):
		if s[current + i] == '1':
			can = 1
			current += i
			result += 1
			break
	if can == 0:
		print(-1)
		exit(0)
print(result)


(n, d) = map(int, input().split())
a = input()
count = 0
dc = d
while True:
	if d < len(a):
		if a[d] == '1':
			count += 1
			a = a[d:]
			d = dc
		elif d == 1:
			print(-1)
			break
		else:
			d -= 1
	else:
		d -= 1
	if d < 1 and count == 0:
		print(-1)
		break
	elif d < 1 and count > 0:
		print(count)
		break


(n, d) = map(int, input().split())
arr = list(input())
count = 0
i = 0
while i < n and i != n - 1:
	k = i + d
	if k >= n:
		k = n - 1
	val = 0
	for j in range(k, i, -1):
		if arr[j] == '1':
			i = j
			val = 1
			count += 1
			break
	if val == 1:
		pass
	else:
		print('-1')
		break
if i == n - 1:
	print(count)
else:
	pass


def main():
	(n, d) = map(lambda x: int(x), input().split(' '))
	lil = input()
	if n <= d:
		res = 1
	else:
		res = jump(n, d, lil)
	print(res)

def jump(n, d, lil):
	currentAt = 0
	nextStop = currentAt + d
	step = 0
	while nextStop < n - 1:
		if lil[nextStop] == '1':
			currentAt = nextStop
			nextStop += d
			step += 1
		else:
			nextStop -= 1
			if nextStop == currentAt:
				return -1
	return step + 1
main()


import array
numbers = list(map(int, input().split()))
n = numbers[0]
d = numbers[1]
dp = []
dp.append(0)
for i in range(1, n):
	dp.append(999999)
s = str(input())
for i in range(1, n):
	if s[i] == '1':
		for j in range(1, d + 1):
			if i - j >= 0:
				dp[i] = min(dp[i - j] + 1, dp[i])
if dp[n - 1] == 999999:
	print('-1')
else:
	print(dp[n - 1])


(n, d) = map(int, input().split())
num = 0
v = 0
a = 1
k = 0
st = input()
for i in range(1, n):
	num += 1
	if int(st[i]) == 1:
		k = num
	if num % d == 0:
		if k != 0:
			num = num - k
			v += 1
		else:
			a = 0
		k = 0
if a == 1:
	if num % d == 0:
		print(v)
	else:
		print(v + 1)
else:
	print(-1)


inp = input().split()
(n, d) = (int(inp[0]), int(inp[1]))
s = input()
b = True
pos = 0
cont = 0
while b and pos < n - 1:
	pos += d
	if pos < n - 1:
		if s[pos] == '0':
			c = True
			for i in range(pos, pos - d, -1):
				if s[i] == '1':
					pos = i
					c = False
					break
			if c:
				b = False
				break
		cont += 1
	else:
		cont += 1
if not b:
	print(-1)
else:
	print(cont)


(length, jump_max) = list(map(int, input().strip().split()))
string = input()
hop = 0
while True:
	if len(string) == 1:
		print(hop)
		break
	try:
		for i in range(jump_max, 0, -1):
			if string[i] == '1':
				hop += 1
				string = string[i:]
				break
		else:
			print(-1)
			break
	except IndexError:
		hop += 1
		print(hop)
		break


(n, d) = map(int, input().split())
a = input()
INF = 9999999999999
dp = [INF] * n
dp[0] = 0
for i in range(1, n):
	if a[i] == '1':
		for j in range(i - d, i):
			dp[i] = min(dp[i], dp[j] + 1)
if dp[n - 1] == INF:
	dp[n - 1] = -1
print(dp[n - 1])


from math import *
from copy import *
from string import *
from random import *
from sys import stdin
from sys import maxsize
from operator import *
from itertools import *
from collections import Counter
import math

def bin1(l, r, k, t, b, val, ans):
	if l > r:
		return ans
	else:
		mid = (l + r) // 2
		v = k ** mid
		if v == val:
			return v
		elif v > val:
			ans = mid
			return bin1(mid + 1, r, k, t, b, val, ans)
		else:
			return bin1(l, mid - 1, k, t, b, val, ans)

def bin2(l, r, k, t, b, val, ans):
	if l > r:
		return ans
	else:
		mid = (l + r) // 2
		v = t * k ** mid + b * mid
		if v == val:
			return v
		elif v > val:
			ans = mid
			return bin2(l, mid - 1, k, t, b, val, ans)
		else:
			return bin2(mid + 1, r, k, t, b, val, ans)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	l = []
	for i in range(2, n + 1):
		if prime[i]:
			l.append(i)
	return l

def bin(l, r, ll, val):
	if l > r:
		return -1
	else:
		mid = (l + r) // 2
		if val >= ll[mid][0] and val <= ll[mid][1]:
			return mid
		elif val < ll[mid][0]:
			return bin(l, mid - 1, ll, val)
		else:
			return bin(mid + 1, r, ll, val)

def deci(n):
	s = ''
	while n != 0:
		if n % 2 == 0:
			n = n // 2
			s = '0' + s
		else:
			n = n // 2
			s = '1' + s
	return s

def diff(s1, s2):
	if len(s1) < len(s2):
		v = len(s1)
		while v != len(s2):
			s1 = '0' + s1
			v = v + 1
	else:
		v = len(s2)
		while v != len(s1):
			s2 = '0' + s2
			v = v + 1
	c = 0
	for i in range(len(s1)):
		if s1[i:i + 1] != s2[i:i + 1]:
			c = c + 1
	return c
from sys import stdin, stdout

def fac(a, b):
	v = a
	while a != b:
		v *= a - 1
		a = a - 1
	return v

def bino(l, r, n):
	if l > r:
		return -1
	else:
		mid = (l + r) // 2
		val1 = math.log(n / mid + 1, 2)
		val2 = int(val1)
		if val1 == val2:
			return val1
		elif val1 < 1.0:
			return bino(l, mid - 1, n)
		else:
			return bino(mid + 1, r, n)

def binary(l, r, ll, val, ans):
	if l > r:
		return ans
	else:
		mid = (l + r) // 2
		if ll[mid] <= val:
			ans = mid + 1
			return binary(mid + 1, r, ll, val, ans)
		else:
			return binary(l, mid - 1, ll, val, ans)
(n, d) = map(int, stdin.readline().split(' '))
s = str(stdin.readline())
if s[n - 1:n] == '0' or s[0:1] == '0':
	print(-1)
else:
	l = []
	for i in range(len(s)):
		if s[i:i + 1] == '1':
			l.append(i + 1)
	if d == 1 and len(l) != n:
		print(-1)
	else:
		i1 = 0
		c = 0
		while i1 < len(l):
			ind = 0
			for i in range(i1 + 1, len(l)):
				if l[i] - l[i1] > d and i == i1 + 1:
					ind = 0
					c = 0
					break
				if l[i] - l[i1] > d:
					break
				else:
					ind = i
			if ind == 0:
				break
			else:
				i1 = ind
				c += 1
		if c == 0:
			print(-1)
		else:
			print(c)


from sys import stdin, setrecursionlimit, stdout
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from heapq import heapify, heappop, heappush, heapreplace, heappushpop

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline().rstrip()

def lsi():
	return list(si())
test_case = 1
while test_case:
	test_case -= 1
	(n, d) = mi()
	a = lsi()
	c = i = j = 0
	while True:
		k = i + d
		while k > j:
			if k >= n - 1:
				print(c + 1)
				exit()
			if int(a[k]):
				break
			k -= 1
		if k == j:
			break
		j = i + d
		i = k
		c += 1
	print(-1)


(n, k) = map(int, input().split())
s = input()
if k >= n:
	print(1)
else:
	(x, f, c) = (0, 0, 0)
	while x < n - 1:
		a = s[x:x + k + 1]
		if '1' not in a[1:]:
			f = 1
			break
		else:
			c += 1
			x += a.rindex('1')
	print([c, -1][f == 1])


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

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

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()

def main():
	(n, d) = LI()
	s = S()
	if s[-1] != '1':
		return -1
	ind = 0
	nxt = d
	cnt = 0
	while True:
		if ind >= n - 1:
			return cnt
		if nxt >= n:
			return cnt + 1
		f = False
		for i in range(ind + 1, nxt + 1)[::-1]:
			if s[i] == '1':
				cnt += 1
				ind = i
				nxt = ind + d
				f = True
				break
		if not f:
			return -1
print(main())


inp = input().split()
n = int(inp[0])
d = int(inp[1])
dp = [-1 for _ in range(n)]
dp[0] = 0
s = input()
for (index, current) in enumerate(s):
	if current == '0' or index == 0:
		continue
	start = 0 if index - d < 0 else index - d
	min_ = float('inf')
	for step in range(start, index):
		if s[step] == '1':
			min_ = min(min_, dp[step])
	dp[index] = min_ + 1
if dp[-1] != float('inf'):
	print(dp[-1])
else:
	print('-1')


(n, d) = map(int, input().split())
p = 0
ls = list(str(input()))
ok = True
tp = 0

def solve(pnt1, pnt2, arr):
	global tp
	pnt2 = min(int(pnt1) + d, n - 1)
	while pnt2 != pnt1 and pnt2 != n - 1:
		if arr[pnt2] == '1':
			pnt1 = int(pnt2)
			tp = max(tp, pnt2)
			return 1 + solve(pnt1, pnt2, arr)
		else:
			pnt2 -= 1
	tp = max(tp, pnt2)
	if arr[pnt2] == '1':
		return 1
	else:
		return 0
ans = solve(0, d, ls)
if tp != n - 1:
	print(-1)
else:
	print(ans)


(points, stepSize) = list(map(int, input().split()))
road = list(map(int, input()))
stepsCount = 0
currentPoint = 0
while currentPoint < points - 1:
	stepFound = False
	if currentPoint >= points - 1:
		break
	tmpStep = stepSize
	while tmpStep >= 1:
		if currentPoint + tmpStep >= points - 1:
			stepsCount += 1
			currentPoint += tmpStep
			stepFound = True
			break
		elif road[currentPoint + tmpStep] == 1:
			stepsCount += 1
			currentPoint += tmpStep
			stepFound = True
			break
		else:
			tmpStep -= 1
	if not stepFound:
		stepsCount = -1
		break
print(stepsCount)


arr = [int(x) for x in input().split()]
h = arr[0]
j = arr[1]
arr = input()
i = 0
count = 0
jump = False
while i < h - 1:
	jump = False
	x = j
	while x > 0:
		if x + i < h:
			if arr[x + i] == '1':
				count += 1
				jump = True
				break
		x += -1
	if jump:
		i = i + x
	else:
		break
if jump:
	print(count)
else:
	print(-1)


(n, d) = map(int, input().split())
ls = input()
(i, j) = (0, 1)
curr_jumps = 0
tot_jumps = 0
ans = 'yes'
while i < n - 1:
	curr_jumps = 0
	while j <= d and i + j < n:
		if ls[i + j] == '1':
			curr_jumps = i + j
		j += 1
	if curr_jumps == 0:
		ans = 'no'
		break
	else:
		tot_jumps += 1
		i = curr_jumps
		j = 1
if ans == 'no':
	print(-1)
else:
	print(tot_jumps)


(n, d) = map(int, input().split(' '))
s = input().strip()
ans = [0 for i in range(n)]
ans[n - 1] = 1
for (idx, val) in enumerate(reversed(s)):
	idx = n - idx - 1
	if val == '1' and ans[idx] != 0:
		for j in range(1, d + 1):
			if idx - j >= 0 and s[idx - j] == '1':
				if ans[idx - j] > ans[idx] + 1 or ans[idx - j] == 0:
					ans[idx - j] = ans[idx] + 1
if ans[0] == 0:
	print(-1)
else:
	print(ans[0] - 1)


def main():
	(n, d) = map(int, input().split())
	mainPath = list(map(int, input().strip()))
	(currentPos, numJumps) = (0, 0)
	while currentPos < n - 1 and numJumps < n:
		if mainPath[currentPos] == 1:
			numJumps += 1
			currentPos += d
		else:
			currentPos -= 1
	if numJumps >= n:
		print(-1)
	else:
		print(numJumps)
main()


(n, e) = map(int, input().split())
s = input()
i = 0
d = e
ans = -1
flag = 0
while i < n - 1:
	if n - i - 1 < e:
		e = n - i - 1
		d = e
	if d == 0:
		flag = 1
		print('-1')
		break
	if s[i + d] == '1':
		i = i + d
		ans += 1
		d = e
	else:
		d -= 1
if flag == 0:
	print(ans + 1)


class axis:

	def __init__(self, lilies):
		self.line = lilies

class frog:

	def __init__(self, d, my_axis):
		self.axis = my_axis
		self.d = d
		self.point = 0

	def jump(self):
		for i in range(self.point + self.d, self.point, -1):
			if i >= len(self.axis.line):
				continue
			if self.axis.line[i] == '1':
				self.point = i
				return True
		return False
(n, d) = [int(i) for i in input().split()]
lilies = input().strip()
my_axis = axis(lilies)
my_frog = frog(d, my_axis)
jump_count = 0
while my_frog.point < n - 1:
	if my_frog.jump():
		jump_count += 1
	else:
		jump_count = -1
		break
print(jump_count)


(n, d) = map(int, input().split())
s = input()
dp = [0] * n
for i in range(n):
	if int(s[i]) == 0:
		dp[i] = 100000
for i in range(d + 1):
	if int(s[i]) != 0:
		dp[i] = 1
for i in range(d + 1, n):
	if int(s[i]) != 0:
		dp[i] = min(dp[i - d:i]) + 1
if dp[n - 1] < 1000:
	print(dp[n - 1])
else:
	print(-1)


def check(present, jump):
	for i in range(jump):
		if row[present + jump - i] == 1:
			present = present + (jump - i)
			return present
	return -1
sj = input().split(' ')
size = int(sj[0])
jump = int(sj[1])
row = input()
row = list(map(int, row))
present = 0
total = 0
while present != size - 1:
	if size - 1 - present < jump:
		total = total + 1
		break
	elif row[present + jump] == 1:
		total = total + 1
		present = present + jump
	else:
		present = check(present, jump)
		if present != -1:
			total = total + 1
		else:
			total = -1
			break
print(total)


(n, d) = list(map(int, input().split()))
a = input()
dp = [float('inf') for i in range(n)]
i = 0
dp[0] = 0
while i < n:
	nxt = i + 1
	if a[i] == '1':
		for j in range(i + 1, min(i + d + 1, n)):
			if a[j] == '1':
				dp[j] = min(dp[j], dp[i] + 1)
				nxt = j
	i = nxt
if dp[n - 1] == float('inf'):
	print('-1')
else:
	print(dp[n - 1])


def read_tokens():
	return input().strip().split()

def read_ints():
	return [int(s) for s in read_tokens()]
(n, d) = read_ints()
arr = input()

def solve(arr: str, d: int) -> int:
	n = len(arr)
	dp = [0] * n
	dp[0] = 0
	for i in range(1, n):
		if arr[i] == '0':
			dp[i] = float('inf')
		else:
			curr_min = dp[i - 1]
			for j in range(2, d + 1):
				if i - j < 0:
					break
				curr_min = min(curr_min, dp[i - j])
			dp[i] = 1 + curr_min
	return dp[n - 1] if dp[n - 1] != float('inf') else -1
print(solve(arr, d))


import sys
(n, d) = map(int, sys.stdin.readline().split())
stri = sys.stdin.readline().strip()

def bfs():
	ds = [-1] * n
	ds[0] = 0
	queue = [0]
	while queue:
		front = queue.pop(0)
		for i in range(front + 1, min(n, front + d + 1)):
			if int(stri[i]) and ds[i] == -1:
				ds[i] = ds[front] + 1
				queue.append(i)
	return ds[-1]
print(bfs())


from sys import stdin, stdout
(n, d) = map(int, stdin.readline().split())
s = stdin.readline().split('\n')[0]
INF = 10 ** 10
dp = [INF for i in range(n)]
dp[0] = 0
for i in range(n):
	if s[i] == '1':
		for j in range(i - 1, max(i - d - 1, -1), -1):
			if s[j] == '1':
				dp[i] = min(dp[j] + 1, dp[i])
ans = dp[n - 1]
if dp[n - 1] == INF:
	ans = -1
stdout.write('{}\n'.format(ans))


(n, k) = [int(t) for t in input().split()]
s = input()
x = [0] * n
for j in range(n):
	if s[j] == '1':
		x[j] = j
	else:
		x[j] = x[j - 1]
pt = 0
c = 0
while pt != n - 1:
	tem = x[min(pt + k, n - 1)]
	c = c + 1
	if tem == pt:
		c = -1
		break
	pt = tem + 1 - 1
print(c)


(n, d) = map(int, input().split())
s = input()
j = 1
v = 0
while j <= n:
	flag = 0
	for i in range(d, 0, -1):
		if i + j - 1 >= n:
			continue
		if s[i + j - 1] == '1':
			j = i + j
			flag = 1
			v += 1
			break
	if flag == 0:
		print(-1)
		exit()
	if j == n:
		print(v)
		exit()
print(-1)


(n, d) = map(int, input().split())
bit = input()
m = len(bit)
a = []
for i in range(n - 1):
	a.append(-1)
a.append(0)
for i in range(n - 2, -1, -1):
	if bit[i] == '1':
		j = 1
		mposs = 1000000
		while j <= d and i + j < n:
			if bit[i + j] == '1' and a[i + j] < mposs and (a[i + j] != -1):
				mposs = a[i + j]
				a[i] = 1 + mposs
			j += 1
print(a[0])


(n, d) = map(int, input().split())
l = list(input())
ans = 0
pos = 1
while pos < n:
	for i in range(d, 0, -1):
		if l[min(pos + i - 1, n - 1)] == '1':
			ans += 1
			pos += i
			break
	else:
		print(-1)
		exit()
print(ans)


x = input().split()
n = int(x[0])
d = int(x[1])
arr = list(input())
frogLocation = 0
jumps = 0
while frogLocation != n - 1:
	x = frogLocation + d
	if x >= n:
		frogLocation = n
		jumps += 1
		break
	while x >= frogLocation:
		if x == frogLocation:
			jumps = -1
			break
		if arr[x] == '1':
			frogLocation = x
			jumps += 1
			break
		x -= 1
	if jumps == -1:
		break
print(jumps)


import sys
[n, d] = [int(x) for x in input().split()]
s = input()
lily = list(map(int, s))
lily.extend([1] * d)
step = 0
frog = 0
while frog < n - 1:
	for i in range(d, 0, -1):
		if lily[frog + i] == 1:
			step += 1
			frog += i
			break
		elif i == 1:
			print(-1)
			sys.exit(0)
print(step)


(n, d) = map(int, input().split())
a = [1000] * (n + 1)
a[0] = 0
s = [int(x) for x in input()]
for x in range(1, n):
	if s[x]:
		for c in range(1, d + 1):
			if x - c >= 0 and s[x - c]:
				a[x] = min(a[x - c] + 1, a[x])
print(-1 if a[n - 1] > 200 else a[n - 1])


(n, d) = map(int, input().split())
s = input().strip()
i = 0
an = 0
while i < n:
	p = i
	for j in range(d, 0, -1):
		if j + i <= n - 1:
			if s[j + i] == '1':
				i = j + i
				an += 1
				break
	if p == i:
		an = -1
		break
	elif i == n - 1:
		break
print(an)


(n, d) = map(int, input().split())
s = input()
if '0' * d in s:
	print(-1)
else:
	ans = 0
	i = 0
	while i < n - 1:
		if list(s)[i] == '1':
			i += d
			ans += 1
		else:
			i -= 1
	print(ans)


(n, d) = list(map(int, input().split()))
s = input()
dp = [0] * len(s)
for i in range(1, d + 1):
	if s[i] == '1':
		dp[i] = 1
dp[0] = 1
for i in range(d + 1, len(s)):
	if s[i] == '0':
		dp[i] = 0
	else:
		curmin = 0
		for j in range(i - d, i):
			if s[j] != '0':
				if curmin == 0 and dp[j] != 0:
					curmin = dp[j]
				elif curmin != 0 and dp[j] != 0:
					curmin = min(curmin, dp[j])
				else:
					continue
		if curmin == 0:
			dp[i] = 0
		else:
			dp[i] = curmin + 1
if dp[-1] != 0:
	print(dp[-1])
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
b = 0
a = []
j = 0
count = 0
for i in s:
	if i == '1':
		a.append(b)
	b = b + 1
p = a[0]
while p != a[len(a) - 1]:
	if p + d < a[j + 1]:
		count = -1
		break
	if p + d in a:
		p = p + d
		count += 1
		j = a.index(p)
		continue
	else:
		p = p - 1
print(count)


(n, d) = map(int, input().split())
is_flower = list(input())
if is_flower[0] == '0':
	print(-1)
else:
	dp = [float('inf') for _ in range(n)]
	dp[0] = 0
	for i in range(n - 1):
		for j in range(i + 1, min(i + d + 1, n)):
			if is_flower[j] == '1':
				dp[j] = min(dp[j], dp[i] + 1)
	if dp[n - 1] == float('inf'):
		print(-1)
	else:
		print(dp[n - 1])


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
(n, d) = map(int, input().split())
a = input()
ans = []
c = 0
i = 0
while i < n - 1:
	best = 0
	for j in range(i + 1, i + d + 1):
		if j < n:
			if a[j] == '1':
				best = j
	if best == 0:
		print(-1)
		break
	else:
		i = best
		c += 1
if best != 0:
	print(c)


x = list(map(int, input().split()))
n = x[0]
d = x[1]
s = input().strip()
s = '0' + s
f = 0
i = 1
jumps = 0
while i <= n and f != 1:
	if d == 1:
		if s.count('0') > 1:
			jumps = -1
			f = 1
		else:
			jumps = n - 1
			f = 1
	else:
		if i + d <= n:
			vari = i + d
		else:
			vari = n
		while vari > i and vari <= n:
			if s[vari] == '1':
				i = vari
				jumps += 1
				if vari == n:
					f = 1
			elif s[vari] == '0':
				vari -= 1
				if vari == i + 1:
					jumps = -1
					f = 1
if jumps == 0:
	jumps = -1
print(jumps)


import sys
from os import path
if path.exists('C:/Users/prana/Desktop/sublime/input.txt'):
	sys.stdin = open('C:/Users/prana/Desktop/sublime/input.txt', 'r')
	sys.stdout = open('C:/Users/prana/Desktop/sublime/output.txt', 'w')

def solve():
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	s = list(input())
	i = 0
	count = 0
	temp = 0
	while i < n - 1:
		j = d
		while j > 0:
			if i + j < n:
				if s[i + j] != '1':
					j -= 1
				else:
					count += 1
					i += j
					break
			else:
				j -= 1
		if j == 0:
			temp = 1
			break
	if temp == 0:
		print(count)
	else:
		print(-1)
T = 1
for _ in range(1, T + 1):
	print('Case #', _, file=sys.stderr)
	solve()


import math

def s():
	(n, d) = [int(x) for x in input().split(' ')]
	arr = input()
	current_pos = 0
	jumps = 0
	while True:
		not_possible = True
		for i in range(d, 0, -1):
			if current_pos + i > n - 1:
				continue
			elif arr[current_pos + i] == '1':
				current_pos += i
				jumps += 1
				not_possible = False
				break
		if not_possible:
			print(-1)
			break
		elif current_pos == n - 1:
			print(jumps)
			break
s()


(a, b) = map(int, input().split())
s = str(input())
count = 0
i = 0
for j in range(1, 10000):
	if s[i] == '1' and i >= a - b - 1:
		break
	if s[i] == '1':
		i = i + b
		count = count + 1
	else:
		i = i - 1
if s[i] == '1' and i >= a - b - 1:
	print(count + 1)
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
dp = [n + 1 for i in range(n)]
dp[0] = 0
for i in range(n):
	if dp[i] != n + 1:
		for jump in range(d, 0, -1):
			if i + jump < n and s[i + jump] == '1':
				dp[i + jump] = min(1 + dp[i], dp[i + jump])
				break
if dp[n - 1] == n + 1:
	print(-1)
else:
	print(dp[n - 1])


class Solution(object):

	def __init__(self):
		pass

	def sol(self, n, td, d, arr, dp):
		if n == 1 and td >= 0:
			return 0
		if td < 0 or n <= 0:
			return 1 << 15
		if (n, td) in dp:
			return dp[n, td]
		one = 1 << 15
		if arr[n - 1] == '1':
			one = self.sol(n - 1, d - 1, d, arr, dp) + 1
		one = min(one, self.sol(n - 1, td - 1, d, arr, dp))
		dp[n, td] = one
		return one

def main():
	p = [int(e) for e in input().split()]
	arr = input()
	sol = Solution()
	r = sol.sol(p[0], 0, p[1], arr, {})
	if r >= 1 << 15:
		print('-1')
	else:
		print(r)
	return 0
main()


L = list(map(int, input().split(' ')))
n = L[0]
d = L[1]
way = input()

def function(n, d, way):
	k = 0
	l = len(way)
	i = 0
	while i < l - 1:
		saute = 0
		for j in range(d, 0, -1):
			if i + j > l - 1:
				j = l - i - 1
				if j < 1:
					i = l + 1
					break
			if way[i + j] == '1':
				i += j
				k += 1
				saute = 1
				break
		if j == 1 and (not saute):
			break
	if i + j < n:
		k = 0
	return k
k = function(n, d, way)
if k == 0:
	print(-1)
else:
	print(k)


(n, d) = map(int, input().split())
abc = input()
count = 0
b = 0
for i in range(0, n):
	i = b
	flag = False
	for j in range(d, 0, -1):
		if i + j <= n - 1 and abc[i + j] == '1':
			b = i + j
			flag = True
			count += 1
			break
	if not flag:
		count = 0
		break
	if b == n - 1:
		break
if count == 0:
	print(-1)
else:
	print(count)


(n, d) = map(int, input().split())
s = input()
l = list()
ind = 1
for c in s:
	if c == '1':
		l.append(ind)
	ind += 1
edges = dict()
for i in range(0, len(l)):
	j = i + 1
	while j < len(l) and l[j] - l[i] <= d:
		if l[i] not in edges:
			edges[l[i]] = list()
		edges[l[i]].append(l[j])
		j += 1
q = list()
q.append(1)
s = 0
e = 1
MAXD = 999999
dist = [MAXD] * (n + 1)
dist[1] = 0
while s < e:
	u = q[s]
	s += 1
	if u not in edges:
		continue
	for v in edges[u]:
		if dist[v] > dist[u] + 1:
			dist[v] = dist[u] + 1
			if v not in q:
				q.append(v)
				e += 1
if dist[n] == MAXD:
	print(-1)
else:
	print(dist[n])


from sys import stdin, stdout
import math, sys, heapq
from itertools import permutations, combinations
from collections import defaultdict, deque, OrderedDict
from os import path
import random
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def I():
		return int(input())

	def In():
		return map(int, input().split())
else:

	def I():
		return int(stdin.readline())

	def In():
		return map(int, stdin.readline().split())

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(n, k) = In()
		l = list(input())
		i = 0
		ans = 0
		flag = 0
		while i < n - 1:
			pos = -1
			for x in range(i + 1, min(i + k + 1, n)):
				if l[x] == '1':
					pos = x
			if pos == -1:
				flag = 1
				break
			else:
				i = pos
			ans += 1
		if flag:
			print(-1)
		else:
			print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


(_, d) = map(int, input().split())
s = input()
curr = 0
result = 0
while curr < len(s) - 1:
	cand = min(curr + d, len(s) - 1)
	while s[cand] == '0':
		cand -= 1
	if cand == curr:
		result = -1
		break
	curr = cand
	result += 1
print(result)


def main():
	(n, d) = map(int, input().split())
	Ox = input()
	pos = 0
	res = 0
	while pos < n - 1:
		new_pos = Ox[pos + 1:pos + 1 + d].rfind('1')
		if new_pos == -1:
			print(-1)
			return
		elif new_pos != -1:
			pos += new_pos + 1
			res += 1
	print(res)
main()


(n, d) = map(int, input().split())
m = input()
jumps = iterator = p = 0
while iterator < n:
	if m[iterator] == '1':
		jumps += 1
		p = iterator
		iterator += d
	else:
		while iterator != p and m[iterator] == '0' or iterator >= n:
			iterator -= 1
		if iterator == p:
			exit(print(-1))
if p != n - 1:
	jumps += 1
print(jumps - 1)


(n, d) = map(int, input().split())
a = list(map(int, input())) + [0] * 200
b = [10 ** 9] * 202
b[0] = 0
for i in range(n):
	for j in range(1, d + 1):
		if a[i] == 1 and a[i + j] == 1:
			b[i + j] = min(b[i] + 1, b[i + j])
print(b[n - 1] if b[n - 1] != 10 ** 9 else -1)


p = list(map(int, input().split()))
a = input()
x = 0
z = p[1]
f = 0
sum = 0
cp = 0
flag = 0
for i in range(1, p[0]):
	if a[i] == '1':
		f = i
	if i - cp >= z or i == p[0] - 1:
		cp = f
		if f != 0:
			sum += 1
			f = 0
		else:
			flag = 1
			break
if flag == 1:
	print('-1')
else:
	print(sum)


from math import inf

def wayhome(string, count, d):
	if len(string) == 0:
		return count
	for i in range(min(d, len(string)) - 1, -1, -1):
		if string[i] == '1':
			mx = wayhome(string[i + 1:], count + 1, d)
			if mx != inf:
				return mx
	return -1
(n, d) = map(int, input().split())
string = input().strip()
x = wayhome(string[1:], 0, d)
print(x)


w = str(input()).split()
n = int(w[0])
d = int(w[1])
ways = str(input())

def num(lis, j):
	if j * str(0) in lis:
		return -1
	elif len(lis) <= j + 1:
		return 1
	else:
		ind = len(lis) + lis[len(lis) - 1 - j:].find('1') - j - 1
		return num(lis[:ind + 1], j) + 1
cara = num(ways, d)
print(cara)


def find_path(n, d, map_):
	cur_i = 0
	jump_count = 0
	end_flag = False
	while not end_flag:
		max_jump = -1
		for i in range(d, 0, -1):
			if cur_i + i < n and fmap[cur_i + i] == '1':
				max_jump = i
				break
		if max_jump == -1:
			end_flag = True
			jump_count = -1
		elif cur_i + max_jump == n - 1:
			end_flag = True
			cur_i += max_jump
			jump_count += 1
		else:
			cur_i += max_jump
			jump_count += 1
	return jump_count
(n, d) = [int(i) for i in input().split(' ')]
fmap = input()
jumps = find_path(n, d, fmap)
print(jumps)


[n, d] = list(map(int, input().split(' ')))
string = input()

def get_best_step(index):
	for i in range(index + d, index, -1):
		if i >= len(string):
			continue
		if string[i] == '1':
			return i
	return -1

def num_steps():
	i = 0
	steps = 0
	while i < len(string):
		if i == len(string) - 1:
			return steps
		i = get_best_step(i)
		if i == -1:
			return -1
		steps += 1
print(num_steps())


(length, jump) = input().strip().split()
plot = input()
(length, jump) = (int(length), int(jump))
n_jumps = 0
pos_index = 0
while pos_index != length - 1:
	land_index = plot[pos_index:pos_index + jump + 1].rfind('1') + pos_index
	if land_index == pos_index:
		n_jumps = -1
		break
	pos_index = land_index
	n_jumps += 1
print(n_jumps)


ND = list(map(int, input().split()))
Array = input()
N = ND[0]
D = ND[1]
ActualPosition = 0
jCount = 0
CheckMove = 0
count = 0
while ActualPosition != N - 1:
	if count == D:
		jCount = -1
		break
	if ActualPosition + D > N - 1:
		D = N - 1 - ActualPosition
	if int(Array[ActualPosition + D - count]) == 1:
		ActualPosition = ActualPosition + D - count
		jCount += 1
		count = 0
	else:
		count += 1
print(jCount)


a = list(map(int, input().strip().split()))
b = input()
pos = 0
step = 0
while pos != a[0] - 1:
	if pos + a[1] >= a[0] - 1:
		if b[-1] == '1':
			step += 1
			pos = a[0] - 1
		else:
			pos = a[0] - 1
			step = -1
	else:
		try:
			out = b[pos + 1:pos + a[1] + 1].rindex('1')
		except:
			step = -1
			pos = a[0] - 1
		else:
			out = b[pos + 1:pos + a[1] + 1].rindex('1')
			step += 1
			pos += out + 1
print(step)


([n, d], s, r, i) = (list(map(int, input().split())), list(map(lambda x: x == '1', list(input()))), 0, 0)
while i != n - 1:
	for j in reversed(range(i, min(i + d + 1, n))):
		if j == i:
			print(-1)
			quit()
		if s[j]:
			i = j
			break
	r += 1
print(r)


x = input().split()
n = int(x[0])
d = int(x[1])
s = input()
flag = False
i = 0
steps = 0
while True:
	j = i + d
	if j >= n - 1:
		flag = True
		steps += 1
		break
	while j > i and s[j] != '1':
		j -= 1
	if j == i:
		break
	i = j
	steps += 1
if flag:
	print(steps)
else:
	print(-1)


(n, k) = map(int, input().split())
s = input()
count = 0
i = 0
while i != n - 1:
	j = min(i + k, n - 1)
	while j > i and s[j] != '1':
		j -= 1
	if i == j:
		count = -1
		break
	else:
		count += 1
		i = j
print(count)


def fun(s, n, d):
	count = 0
	i = 0
	while i < n - 1:
		j = i + d
		while j >= n:
			j -= 1
		while s[j] != '1':
			j -= 1
		if j == i:
			return -1
		count += 1
		i = j
	return count
(n, d) = list(map(int, input().split()))
s = input()
print(fun(s, n, d))


def solve(n, d, s):
	if len(s) <= d or len(s) - 1 == d:
		return 1
	indices = []
	for i in range(1, d + 1):
		if s[i] == '1':
			indices.append(i)
	if len(indices) == 0:
		print(-1)
		exit(0)
	index = max(indices)
	ans = solve(n - index, d, s[index:]) + 1
	return ans
tmp = input().split(' ')
n = int(tmp[0])
d = int(tmp[1])
s = input()
ans = solve(n, d, s)
print(ans)


(n, k) = map(int, input().split())
s = str(input())
mas = [1000000000.0] * (n + 1)
mas[0] = 0
for i in range(n):
	if s[i] == '1':
		for j in range(min(n, i + k + 1)):
			if s[j] == '1':
				mas[j] = min(mas[i] + 1, mas[j])
print(mas[n - 1] if mas[n - 1] != 1000000000.0 else -1)


(n, k) = map(int, input().split())
l = input()
d = [0] * n
for i in range(n - 2, -1, -1):
	if l[i] == '1':
		if i + k >= n - 1:
			d[i] = 1
		else:
			f = float('inf')
			for j in range(i + 1, min(i + k + 1, n - 1)):
				if l[j] == '1' and d[j] != 0:
					f = min(f, d[j] + 1)
			if f != float('inf'):
				d[i] = f
if d[0]:
	print(d[0])
else:
	print(-1)


(n, d) = map(int, input().split())
s = input()
(i, t) = (0, 0)
jumps = 0
while i != n - 1:
	i += d
	jumps += 1
	if i >= n - 1:
		break
	t = i - d
	while s[i] != '1' and i != t:
		i -= 1
	if i == t:
		break
if i != t:
	print(jumps)
else:
	print(-1)


def df(q, st):
	global k, g
	g = st
	if q[st]:
		k += 1
		df(q, max(q[st]))
	return st
(n, d) = map(int, input().split())
s = input()
q = [set() for i in range(n)]
for i in range(n):
	for j in range(i + 1, min(n, d + i + 1)):
		if s[i] == '1' == s[j]:
			q[i].add(j)
(k, g) = (0, 0)
df(q, 0)
if g == n - 1:
	print(k)
else:
	print(-1)


def main():
	(n, d) = map(int, input().split())
	s = input()
	(cur, jumps) = (1, 0)
	while cur < n:
		jumped = False
		for step in range(1, d + 1)[::-1]:
			if cur + step > n:
				continue
			if s[cur + step - 1] == '1':
				cur += step
				jumps += 1
				jumped = True
				break
		if not jumped:
			print(-1)
			return
	print(jumps)
main()