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 \le n, k \le 2 \cdot 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$.

Difficulty: introductory

Starter code:

Solutions:
import heapq

n, k = list(map(int, input().split()))
s = input()

mostRecent = n
best = []
for room in range(n-1, -1, -1):
    if s[room] == '1':
        mostRecent = room
    best.append(mostRecent)

best = best[::-1]

dp = [0]

vals = [(0,0)]

for room in range(1, n + 1):
    new = dp[-1] + room
    if room - k - 1 >= 0:
        bestRout = best[room - k - 1]
        if bestRout <= (room - 1):
            covered = bestRout - k

            if covered >= 0:
                try:
                    while len(vals) > 0 and vals[0][1] < covered:
                        heapq.heappop(vals)
                    if len(vals) > 0:
                        add = vals[0][0]
                        new2 = (bestRout + 1) + add
                        new = min(new2, new)
                except Exception:
                    pass
            else:
                new2 = (bestRout + 1)
                new = min(new2, new)



    dp.append(new)
    heapq.heappush(vals, (new, room))

print(new)
    


def get(n,k,s):
    nxt=[0]*(n+1)
    cur=1<<30
    for i in range(n,0,-1):
        if s[i-1]=='1':
            cur=i
        nxt[i]=cur
    
    dp=[0]
    for i in range(1,n+1):
        dp.append(dp[-1]+i)
        c=nxt[max(i-k,1)]
        if c<=i+k:
            dp[i]=min(dp[i],dp[max(1,c-k)-1]+c)
    
    return dp[n]
n,k=list(map(int,input().split()))
s=input()
print(get(n,k,s))


import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
s=input().strip()


seg_el=1<<((n+k+1).bit_length())# Segment treeの台の要素数
SEG=[1<<40]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def getvalue(n,seg_el):
    i=n+seg_el
    ANS=1<<40
    
    ANS=min(SEG[i],ANS)
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS=min(SEG[i],ANS)
        i>>=1

    return ANS

def updates(l,r,x):# 区間[l,r)に関するminを調べる
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=min(x,SEG[L])
            L+=1

        if R & 1:
            R-=1
            SEG[R]=min(x,SEG[R])
        L>>=1
        R>>=1

updates(n,n+k+1,0)

for i in range(n-1,-1,-1):
    if s[i]=="0":
        x=getvalue(i+1,seg_el)
        updates(i,i+1,x+i+1)
    else:
        x=getvalue(i+k+1,seg_el)
        updates(max(0,i-k),i+k+1,x+i+1)
    
print(getvalue(0,seg_el))



n, k = tuple(map(int, input().rstrip().split()))
s = input().rstrip()
cur = int((2*pow(10,5)) * (2*pow(10,5) + 1) / 2) + 1
cost = [0] * (n+1)
dp = [0]

for i in range(n, 0, -1):
    if s[i-1] == '1':
        cur=i
    cost[i]=cur


for i in range(1, n+1):
    dp.append(dp[-1] + i)
    cs = cost[max(i-k, 1)]
    if cs <= i+k:
        dp[i] = min(dp[i], dp[max(1, cs-k)-1]+cs)
    
print(dp[n])


from operator import itemgetter


class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 10**18
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


n, k = map(int, input().split())
s = input()
info = []
for i, char in enumerate(s):
    if char == "0":
        info.append((i, i+1, i+1))
    else:
        info.append((max(i-k, 0), min(i+k+1, n), i+1))
info = sorted(info, key = itemgetter(1))

st = SegmentTree(n+1)
for begin, end, cost in info:
    if begin == 0:
        tmp = min(st.get_min(end - 1, end), cost)
    else:
        tmp = min(st.get_min(end - 1, end), st.get_min(begin - 1, end) + cost)
    st.update(end - 1, tmp)
print(st.get_min(end - 1, end))

from heapq import heappush, heappop
from collections import deque
N, K = map(int, input().split())
*B, = map(int, input())

INF = 10**18
que = deque()
hq = []
dp = [INF]*(N+1)
dp[0] = 0
for i in range(N):
    a = dp[i]
    while hq and hq[0][1] < i:
        heappop(hq)
    if hq:
        a = min(hq[0][0], a)
    #print(i, a)

    while que and a <= que[-1][1]:
        que.pop()
    que.append((i, a))

    if B[i]:
        heappush(hq, (que[0][1] + (i+1), i+K+1))

    if que and que[0][0] <= i-K:
        que.popleft()
    dp[i+1] = a + (i+1)
while hq and hq[0][1] < N:
    heappop(hq)
a = dp[N]
if hq:
    a = min(hq[0][0], a)
print(a)

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

a = list(map(str, input().strip()))

ans = 0
import math
from collections import deque

dp = [math.inf] * (n + 10)
dp[n + 1] = 0
next = [n + 1] * (n + 10)
now = deque()
for i in range(n):
    if a[i] == '1':
        now.append(i + 1)
    if len(now) == 0:
        continue
    if now[0] + k < i + 1:
        now.popleft()
    if len(now):
        next[i + 1] = now[0]

cur = n + 1
for i in range(n - 1, -1, -1):
    if a[i] == '1':
        cur = i + 1
    if cur - i - 1 <= k:
        next[i + 1] = min(next[i + 1], cur)

for i in range(n, 0, -1):
    dp[i] = min(dp[i], dp[i + 1] + i)
    if next[i] != n + 1:
        dp[max(next[i] - k, 1)] = min(dp[max(next[i] - k, 1)], dp[i + 1] + next[i])

print(dp[1])


def main():
    while True:
        try:
            n, m = map(int, input().strip().split())
            s = str(input())
            print(getAns(n, m, s))
        except EOFError:
            break

def getAns(n, k, s):
    ans = [0] * (n + 10)
    
    s = '0' + s
    ans[0] = 0
    lrt = 0
    for i in range(1, n+1, 1):
        while (lrt < i and (lrt < i - k or s[lrt]=='0')):
            lrt += 1
#        print('nb', s[lrt], i, lrt)
        ans[i] = ans[max(0, lrt-k-1)]+lrt if s[lrt]=='1' else ans[i-1]+i
        if s[i] == '1':
            for j in range(i-1, -1, -1):
                if s[j] == '1':
                    break
                ans[j] = min(ans[j], ans[i])
                
#    print(ans)
    return ans[n]


def __starting_point():
    main()
__starting_point()


n, k = list(map(int, input().split()))
mask = list(map(int, input()))

dp = [0] * (n + 2)
nxt = [1 << 31] * (n + 2)

for i in range(n, 0, -1):
    nxt[i] = i if mask[i - 1] is 1 else nxt[i + 1]

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + i
    idx = nxt[max(1, i - k)]
    if idx <= i + k:
        dp[i] = min(dp[i], dp[max(0, idx - k - 1)] + idx)

print(dp[n])



def find(roomcount,radius,string):
    zero_roomcount=[0]*(roomcount+1)
    binary_move=1<<1000#сдвиг двоичной единицы на 1000 влево или любое число
    for i in range(roomcount,0,-1):
        if string[i-1]=='1':
            binary_move=i
        zero_roomcount[i]=binary_move
    dp=[0]
    for i in range(1,roomcount+1):
        dp.append(dp[-1]+i)
        c=zero_roomcount[max(i-radius,1)]
        if c<=i+radius:
            dp[i]=min(dp[i],dp[max(1,c-radius)-1]+c)  
    return dp[roomcount]
roomcount,radius=map(int,input().split())
string=input()
print(find(roomcount,radius,string))

n, k = map(int, input().split())
s = input()
inf = 10**18
who = [-1] * n
for i in range(n):
  if s[i] == '1':
    for j in range(min(n - 1, i + k), i - 1, -1):
      if who[j] == -1:
        who[j] = i
      else:
        break
for i in range(n):
  if s[i] == '1':
    for j in range(i - 1, max(-1, i - k - 1), -1):
      if who[j] == -1:
        who[j] = i
      else:
        break
dp = [inf] * (n + 1)
dp[n] = 0
for i in range(n, 0, -1):
  dp[i - 1] = min(dp[i - 1], dp[i] + i)
  if who[i - 1] != -1:
    dp[max(0, who[i - 1] - k)] = min(dp[max(0, who[i - 1] - k)], dp[i] + who[i - 1] + 1)
print(dp[0])

def __starting_point():
    n, dist = list(map(int, input().split()))
    light = input().strip()
    right_cover = 0
    left_most = [-1]*(n)
    for idx, ele in enumerate(light):
        if ele == '1':
            for i in range(max(right_cover, idx-dist), min(idx + dist + 1, n)):
                left_most[i] = idx
            right_cover = idx + dist + 1
    dp = [0]*(2*n+1)
    for i in range(n):
        dp[i] = 1000000000000000000

    for idx in range(n-1, -1, -1):
        dp[idx] = min(dp[idx+1] + idx + 1, dp[idx])
        if left_most[idx] != -1:
            left = left_most[idx]
            dp[max(left-dist, 0)] = min(dp[idx+1] + left + 1, dp[max(left-dist, 0)])
            dp[idx] = min(dp[max(left-dist, 0)], dp[idx])
    print(dp[0])

__starting_point()

import os
import sys


def solve(is_router, k):
    n = len(is_router)
    router_stack = [idx + 1 for idx, r in enumerate(is_router) if r == 1][::-1]
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        c = dp[i - 1] + i
        while router_stack and router_stack[-1] + k < i:
            router_stack.pop(-1)

        if router_stack and router_stack[-1] - k <= i <= router_stack[-1] + k:
            t = router_stack[-1]
            dp[i] = min(t + dp[max(0, t - k - 1)], c)
        else:
            dp[i] = c

    return dp[-1]


def pp(input):
    n, k = list(map(int, input().strip().strip().split()))
    is_router = list(map(int, input().strip()))
    print(solve(is_router, k))


if "pydev" in sys.argv[0]:
    from string_source import string_source, codeforces_parse

    x = """inputCopy
5 2
00100
outputCopy
3
inputCopy
6 1
000000
outputCopy
21
inputCopy
4 1
0011
outputCopy
4
inputCopy
12 6
000010000100
outputCopy
15"""

    for q, a in codeforces_parse(x):
        pp(string_source(q))
        print(a)
        print("----")
else:
    pp(sys.stdin.readline)


from collections import deque

def ans(n,k,a):
    dp = [0 for i in range(n+1)]
    q = deque()
    for i in range(1,n+1):
        r = None
        while len(q) > 0:
            cur = q[0]
            if i <= cur+k:
                r = cur
                break
            q.popleft()
        if a[i-1]=='0':
            if r != None:
                dp[i] = min(r+dp[max(0,r-k-1)],r+dp[r-1])
            else:
                dp[i] = i+dp[i-1]
        else:
            q.append(i)
            if r!=None:
                dp[i] = min(i+dp[max(0,i-k-1)],r+dp[max(0,r-k-1)],r+dp[r-1])
            else:
                dp[i] = min(i+dp[max(0,i-k-1)],i+dp[i-1])
    return dp[n]    


n,k = list(map(int,input().split(" ")))
a = input()
out = ans(n,k,a)
print(out)

from collections import deque

def ans(n,k,a):
    dp = [0 for i in range(n+1)]
    q = deque()
    for i in range(1,n+1):
        r = None
        while len(q) > 0:
            cur = q[0]
            if i <= cur+k:
                r = cur
                break
            q.popleft()
        if a[i-1]=='0':
            if r != None:
                dp[i] = min(r+dp[max(0,r-k-1)],r+dp[r-1])
            else:
                dp[i] = i+dp[i-1]
        else:
            q.append(i)
            if r!=None:
                dp[i] = min(i+dp[max(0,i-k-1)],r+dp[max(0,r-k-1)],r+dp[r-1])
            else:
                dp[i] = min(i+dp[max(0,i-k-1)],i+dp[i-1])
    return dp[n]    


n,k = list(map(int,input().split(" ")))
a = input()
out = ans(n,k,a)
print(out)  

n, k = (int(i) for i in input().split())
string = input()

INF = 10**100
cache = [INF] * n
def getVal(idx):
    if idx < 0 or cache[idx] == INF:
        return 0
    return cache[idx]

last_idx = 0
reached_end = False
for i in range(n):
    if string[i] == '0':
        new = getVal(i-1)+i+1
        cache[i] = min(cache[i], new)
    else:
        new = getVal(i-1-k)+i+1
        if new < cache[i]:
            cache[i] = new
            last_idx = 0

        if reached_end:
            continue
        end = i+k+1
        if end >= n:
            end = n
            reached_end = True
        for j in range(max(last_idx, i-k), end):
            cache[j] = min(new, cache[j])
        last_idx = end
print(cache[n-1])