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: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
(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])


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)


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\n5 2\n00100\noutputCopy\n3\ninputCopy\n6 1\n000000\noutputCopy\n21\ninputCopy\n4 1\n0011\noutputCopy\n4\ninputCopy\n12 6\n000010000100\noutputCopy\n15'
	for (q, a) in codeforces_parse(x):
		pp(string_source(q))
		print(a)
		print('----')
else:
	pp(sys.stdin.readline)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
s = input().strip()
seg_el = 1 << (n + k + 1).bit_length()
SEG = [1 << 40] * (2 * seg_el)

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


def find(roomcount, radius, string):
	zero_roomcount = [0] * (roomcount + 1)
	binary_move = 1 << 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))


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
		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])
	return ans[n]
main()


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


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


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


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


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


(n, dist) = 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])


from operator import itemgetter

class SegmentTree:

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


mod = 10 ** 9 + 7
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
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):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def ain():
	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)
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')
main()


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


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, k) = kk()
s = input()
curr = n + k + 1
lmr = [0] * n
for i in range(n - 1, -k - 1, -1):
	if i > -1 and s[i] == 49:
		curr = i
	if i + k < n:
		lmr[i + k] = curr
dp = [n * n] * (n + 1)
dp[n] = 0
for i in range(n, 0, -1):
	dp[i - 1] = min(dp[i - 1], dp[i] + i)
	if lmr[i - 1] - (i - 1) <= k:
		lm = max(0, lmr[i - 1] - k)
		dp[lm] = min(dp[lm], dp[i] + lmr[i - 1] + 1)
print(dp[0])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		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')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from heapq import heappop, heappush
from math import inf
for _ in range(int(input()) if not True else 1):
	(n, k) = map(int, input().split())
	s = input()
	cur = 0
	queue = []
	ans = [inf] * n
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			ans[i] = i + 1
		else:
			ans[i] = min(ans[i], ans[i + 1] + i + 1)
		to_push = None
		if s[i] == '1':
			ans[i] = min(ans[i], ans[i + k + 1] + (i + 1) if i + k + 1 < n else i + 1)
			to_push = (ans[i], i - k)
		while queue:
			(value, index) = heappop(queue)
			if index > i:
				continue
			ans[i] = min(ans[i], value)
			heappush(queue, (value, index))
			break
		if to_push:
			heappush(queue, to_push)
	print(ans[0])


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)