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 ≤ n, r ≤ 1000) — the number of elements in the array and the value of heaters.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 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.
'''
We could find minimum number of heaters required to heat up each element in house by using
following strategy:

Turn on all heaters, check if all elements covered, if not print -1.

After all heaters turned on, let's minimize them by removing non-essentials heaters. What is
exactly non-essentials heaters? Basically if we turned off this heater, every element would be
still covered in heat. To find this non-essentials heaters, basically we just need to find
the heaters which in its all covered elements has more than one source of heat. So if in the
covered elements there is a single element which only has one source, this means that the heaters
is essentials so it cannot be turned off.

So basically to find minimum number of heaters we just need to turn off all the non essentials
heaters.
'''

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

counts = [0] * n # contains number of element heat source in array
heaters = [] # contains index of heaters in array

# turn on all heaters, take a note number of heat source for each
# element in array
for i in range(0, n):
    if arr[i] == 0:
        continue
    heaters.append(i)
    for j in range(max(0, i - r+1), min(n-1,i+r-1)+1):
        counts[j] += 1

if 0 in counts:
    # not every element could be covered in heat, print -1
    print(-1)
else:
    # find essential heaters
    ret = len(heaters)
    for i in range(0, len(heaters)):
        heater_idx = heaters[i]
        found = False
        for j in range(max(0, heater_idx-r+1),min(n-1,heater_idx+r-1)+1):
            # found essential heater
            if counts[j] == 1:
                found = True
                break
        
        # if not essential heater, turn it off
        if not found:
            # turn off heater
            ret -= 1
            # update number of source heat in heater covered elements
            for j in range(max(0, heater_idx-r+1),min(n-1,heater_idx+r-1)+1):
                counts[j] -= 1      
    # print number of essential heaters
    print(ret)