1216_F. Wi-Fi
You work as a system administrator in a dormitory, which has n rooms one after another along a straight hallway. Rooms are numbered from 1 to n.

You have to connect all n rooms to the Internet.

You can connect each room to the Internet directly, the cost of such connection for the i-th room is i coins. 

Some rooms also have a spot for a router. The cost of placing a router in the i-th room is also i coins. You cannot place a router in a room which does not have a spot for it. When you place a router in the room i, you connect all rooms with the numbers from max(1,~i - k) to min(n,~i + k) inclusive to the Internet, where k is the range of router. The value of k is the same for all routers. 

Calculate the minimum total cost of connecting all n rooms to the Internet. You can assume that the number of rooms which have a spot for a router is not greater than the number of routers you have.

Input

The first line of the input contains two integers n and k (1 ≤ n, k ≤ 2 ⋅ 10^5) — the number of rooms and the range of each router.

The second line of the input contains one string s of length n, consisting only of zeros and ones. If the i-th character of the string equals to '1' then there is a spot for a router in the i-th room. If the i-th character of the string equals to '0' then you cannot place a router in the i-th room.

Output

Print one integer — the minimum total cost of connecting all n rooms to the Internet.

Examples

Input


5 2
00100


Output


3


Input


6 1
000000


Output


21


Input


4 1
0011


Output


4


Input


12 6
000010000100


Output


15

Note

In the first example it is enough to place the router in the room 3, then all rooms will be connected to the Internet. The total cost of connection is 3.

In the second example you can place routers nowhere, so you need to connect all rooms directly. Thus, the total cost of connection of all rooms is 1 + 2 + 3 + 4 + 5 + 6 = 21.

In the third example you need to connect the room 1 directly and place the router in the room 3. Thus, the total cost of connection of all rooms is 1 + 3 = 4.

In the fourth example you need to place routers in rooms 5 and 10. Then all rooms will be connected to the Internet. The total cost of connection is 5 + 10 = 15.
```python
mod=10**9+7
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
from bisect import bisect_right as br             #c++ upperbound
import itertools
import collections
import math
import heapq
from random import randint as rn
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):                        #for using this uncomment the lines calculating fact and ifact
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x
"""*******************************************************"""
def main():
	n,k=map(int,input().split())
	s=sin()
	q=[]
	g=[0]
	for i in range(1,n+1):
		g.append(g[i - 1] + i)
	f=[0]*200001
	mi = 1000000000000000
	ans = g[n];
	z=0
	for i in range(1,n+1):
		if (s[i-1] == '0'):
		    continue
		f[i] = g[max(0, i - k - 1)] + i;
		while (len(q)>0 and z<len(q) and q[z] < i - 2 * k - 1):
			mi = min(mi, f[q[z]] - g[q[z] + k])
			z+=1
		if (len(q)>0 and z<len(q)):
		    f[i] = min(f[i], f[q[z]] + i)
		if (i > k):
		    f[i] = min(f[i], g[i - k - 1] + mi + i)
		while (len(q)>0 and f[-1] > f[i]): 
		    q.pop()
		q.append(i)
		ans = min(ans, g[n] - g[min(n, i + k)] + f[i]);
	print(ans)
######## Python 2 and 3 footer by Pajenegod and c1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
 
if __name__ == '__main__':
    main()
#threading.Thread(target=main).start()

```