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.

Difficulty: interview

Starter code:

Solutions:
'''input
4 2
1001
'''

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 = [int(i) for i in input().split()]
a = input()
dp = [1e9] * 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] != 1e9 else -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':
			#print(j)
			f = 1
			i = j
			t = t+1
			break
if f == 0 :
	print(-1)
else:
	print(t)
			


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])


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)

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 = 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=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
      else:
            if '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

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)

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)


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
				#if d+a-r<len(s):
			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:
				#	while d+a-r>=len(s):
				#		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,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)
        #print(p,pp)
        return
    else:
        p=pp
        ans+=1
print(ans)

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)


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=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()))
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

            else:
                if a[pos + i - 1] == "1":
                    pos += i
                    out += 1
                    break

print(out)

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)



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

num = 0 #distance from the last step
v = 0 #value of steps
a = 1 #flag for excistence
k = 0 #coord. of the last step variant destination

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)

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])

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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()

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 23 03:02:56 2017

@author: sherlock
"""

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])

#for i in range(0,n):
 #   print(dp[i])

if(dp[n-1]==999999):
    print("-1")
else: 
    print(dp[n-1])




n, d = list(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)
        return
    elif '1' in place:
        a += k-place[::-1].index('1')
        x+=1
    else:
        print(-1)
        return


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)

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math, fractions, collections
# ===================================
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

	# print(i, ans)

	if i == n-1 or not(flag):
		break

if i+1 == n:
	print(ans)
else:
	print(-1)


def solve():
	n, d = list(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()