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

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

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

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

Initially, all the heaters are off.

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

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


-----Input-----

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

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


-----Output-----

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


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

Output
3

Input
5 3
1 0 0 0 1

Output
2

Input
5 10
0 0 0 0 0

Output
-1

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

Output
3



-----Note-----

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

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

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

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

Difficulty: introductory

Starter code:

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




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

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

mainB()

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

count = 0
position = 0
last_seen_heater = -1

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

print(count)

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

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

i=0

d=0

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


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


import sys

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


count=0
i=0
while i<n:

    for j in range(min(i+r-1,n-1),max(i-r,-1),-1):
        if A[j]==1:
            count+=1

            if j+r>i:
                i=j+r
                break
            else:
                print(-1)
                return

    else:
        print(-1)
        return


print(count)

            
    
    


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

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

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


n, r = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

enabled = [0]*n
ans = 0
i = 0
breaked = False
while i < n:
    j = i + r - 1
    
    heater = -1
    while j >= i-r+1:
        if j>=0 and j < n and a[j] == 1:
            heater = j
            break
        j -= 1
    #print(heater)
    if heater == -1:
        breaked = True
        break
    else:
        i = heater + r
    ans += 1
    
if not breaked:
    print(ans)
else:
    print(-1)


def main():
    n, r = list(map(int, input().split()))
    arr = [True if c == '1' else False for c in input().split()]
    #print(arr)

    last_heated = 0
    tot = 0
    last_turned = -1
    while last_heated < n:
        optim = last_heated + r - 1

        while True:
            if optim < 0:
                print('-1')
                return
            if optim <= last_turned:
                print('-1')
                return
            if optim >= n:
                optim -= 1
                continue
            if arr[optim]:
                # found a heater
                tot += 1
                last_heated = optim + r
                last_turned = optim
                #print('turn on ' + str(optim))
                break
            optim -= 1
    print(tot)


def __starting_point():
    main()

__starting_point()

'''input
5 10
0 0 0 0 0
'''
from sys import stdin, stdout

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

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

def pylons(k,arr):
	count=0; i=0
	while i<len(arr):
		index_right=right_index_search(i,arr,k)
		#print(index_right)
		if index_right==-1:
			index_left=left_index_search(i,arr,k)
			if index_left==-1:
				return -1
			else:
				i=index_left+k
				count+=1 
		else:
			i= index_right+k
			count+=1
	return count

def __starting_point():
    n, k = input().strip().split(' ')
    n, k = [int(n), int(k)]
    arr = list(map(int, input().strip().split(' ')))
    result = pylons(k, arr)
    print(result)


__starting_point()

n,r=[int(x) for x in input().split()]
ns=[int(x) for x in input().split()]
def fin(i):
    p=need+r-1
    last=max(need-r,-1)
    j=min(len(ns)-1,p)
    while j>last:
        if ns[j]>0:
            return j+r
        j-=1
    return -1
need=0
ans=0
while need<len(ns):
    ans+=1
    need=fin(need)
    if need==-1:
        print(-1)
        quit()
print(ans)



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

def f():
    prev = [0]*n
    last = -1
    for i in range(n):
        if a[i]:
            last = i
        prev[i] = last

    nb = 0
    i = 0
    while i < n:
        # find the rightmost heater covering i
        j = prev[min(i + r, n - 1)]
        if j < 0 or j + r < i:
            return -1
        nb += 1
        # next place to heat is the first not covered by the selected heater
        i = j + r + 1

    return nb

print(f())



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

heaters = list(map(int, input().split(' ')))
heated = [0] * len(heaters)

heaters_cnt = 0
i = 0
while i < len(heated):
    flag = False
    for j in range(r-1, -r, -1):
        if heaters[max(0, min(i + j, n-1))] == 1:
            heaters_cnt += 1
            flag = True
            i = i + j + r
            break

    if not flag:
        heaters_cnt = -1
        break

print(heaters_cnt)

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

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

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

masn = [0 for i in range(n)]

for i in range(n):
    if mas[i]==1:
        for j in range(max(0, i-r+1), min(n, i+r)):
            masn[j]=i+1

ind=0
otv=0
br = False
while (ind<n):
    if masn[ind]>0:
        otv+=1
        ind = masn[ind]-1+r
    else:
        br = True
        break
if br: print(-1)
else: print(otv)


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

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

print(res)




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

        if b:
            ans+=1

if c.count(0)==0:
    ans=1;i=0
    for j in range(r-1,-1,-1):
        if j>=n:
            continue
        if l[j]==1:
            i=j
            break
    while True:
        #print(i)
        if i+r-1>=n-1:
            break

        for j in range(i+2*(r-1)+1,i,-1):
            if j>=n:
                continue
            if l[j]==1:
                ans+=1
                i=j
                break

        if i+r-1>=n-1 or (i==n-1):
            break
    print(ans)

else:
    print(-1)

n, r = list(map( int, input().split() ))
a = [ 0 ] + list( map( int, input().split() ) )

l = 0
i = 1
end = 0
while i <= n:
    j = i + r - 1
    j = min( j, n )
    while j >= end and j <= n and a[ j ] < 1:
        j -= 1
    if j > end:
        l += 1
        end = j
        i = j + r
    else:
        l = -1
        break

print( l )


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