Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[0]
        cur_y = current[1]

        for i in range(len(dx)):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_x][next_y] == float('inf'):
                dist[next_x][next_y] = dist[cur_x][cur_y] + 1
                blacks.append((next_x, next_y))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()
import math
n = int(input())
ln = int(math.log10(n))
#1つ下の桁がない場合
if ln == 0:
  print(n)
#全ての桁が9の場合
elif (n+1) % (10 ** (ln + 1)) == 0:
  print(9 * (ln + 1))
#それ以外
else:
  a = n // (10 ** ln)
  b = a * (10 ** ln )- 1
  c = [int(x) for x in list(str(b))]

  print(sum(c))

### FIXED CODE ###

import math
n = int(input())
k = int(math.log10(n))

a = n // (10 ** k)
b = n % (10 ** k)

if k == 0:
  ans = n
elif n % 10 == 9:
  ans = k * 9 + a
else:
  ans = k * 9 + a -1

print(ans)
r, c = map(int, input().strip().split())
l = [[] for i in range(r)].append([0 for j in range(c+1)])
for i in range(r):
    l[i] = list(map(int, input().strip().split()))
    l[i].append(sum(l[i][0:c]))
    l[r] = [l[r][j] + l[i][j] for j in range(c+1)]
    print(' '.join(map(str,l[i])))
print(' '.join(map(str,l[r])))

### FIXED CODE ###

r, c = map(int, input().strip().split())
l = [[0 for j in range(c+1)] for i in range(r+1)]
for i in range(r):
    l[i] = list(map(int, input().strip().split()))
    l[i].append(sum(l[i][0:c]))
    l[r] = [l[r][j] + l[i][j] for j in range(c+1)]
    print(' '.join(map(str,l[i])))
print(' '.join(map(str,l[r])))
n,k = map(int, input().split())
a = list(map(int, input().split()))
setA = set(a)
c = Counter(A)
ans = 0

for w, v in sorted(c.items(), key=lambda x: x[1]):
    if k < len(set(a)):
        while w in a:
            aIndex = a.index(w)
            a.pop(aIndex)
            ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter

N,K = map(int, input().split())
A = list(map(int, input().split()))

c = Counter(A)
d = sorted(c.values())
l = len(d)
print(sum(d[0:l-K]))
import math
import sys

import numpy as np
from scipy.optimize import minimize


scan = sys.stdin.readline


def main():
    l = int(scan().rstrip())

    v = lambda x, n: (x[0] ** 2) * x[1] + (x[1] ** 2) * x[0] - n * x[0] * x[1]
    cons = (
        {"type": "ineq", "fun": lambda x: x[0]},
        {"type": "ineq", "fun": lambda x: x[1]},
        {"type": "ineq", "fun": lambda x: l - x[0] - x[1]}
    )

    result = minimize(v, x0=np.array([l/3, l/3]), constraints=cons, method="SLSQP")
    print(result["fun"][0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import sys

import numpy as np
from scipy.optimize import minimize


scan = sys.stdin.readline


def main():
    l = int(scan().rstrip())

    v = lambda x: (x[0] ** 2) * x[1] + (x[1] ** 2) * x[0] - l * x[0] * x[1]
    cons = (
        {"type": "ineq", "fun": lambda x: x[0]},
        {"type": "ineq", "fun": lambda x: x[1]},
        {"type": "ineq", "fun": lambda x: l - x[0] - x[1]}
    )

    result = minimize(v, x0=np.array([l/3, l/3]), constraints=cons, method="SLSQP")
    print(-result["fun"])


if __name__ == '__main__':
    main()
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X, Y, A, B, C = LI()
p = LI()
q = LI()
r = LI()

p.sort(reverse= 1)
q.sort(reverse= 1)
r.sort(reverse= 1)

def solve():
    ans = 0
    p_selected = p[:X]
    q_selected = q[:Y]
    p_selected.sort()
    q_selected.sort()
    p_cnt = 0
    q_cnt = 0
    r_selected = r[:(X + Y)]
    # print(p_selected, q_selected)

    ans += sum(p_selected) + sum(q_selected)
    for r_i in r_selected:
        if p_selected[p_cnt] > q_selected[q_cnt] and q_cnt < Y:
            if q_selected[q_cnt] < r_i:
                ans += r_i - q_selected[q_cnt]
                q_cnt += 1

            else:
                return ans
        else:
            if p_selected[p_cnt] < r_i:
                ans += r_i - p_selected[p_cnt]
                p_cnt += 1
            else:
                return ans
    return ans

ans = solve()

print(ans)

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X, Y, A, B, C = LI()
p = LI()
q = LI()
r = LI()

p.sort(reverse= 1)
q.sort(reverse= 1)
r.sort(reverse= 1)

def solve():
    ans = 0
    p_selected = p[:X]
    q_selected = q[:Y]
    p_selected.sort()
    q_selected.sort()
    p_cnt = 0
    q_cnt = 0
    r_selected = r[:min((X + Y), len(r))]
    # print(p_selected, q_selected)

    ans += sum(p_selected) + sum(q_selected)
    for r_i in r_selected:
    
        if q_cnt < Y and p_cnt < X:
            if p_selected[p_cnt] >= q_selected[q_cnt]:
                if q_selected[q_cnt] < r_i:
                    ans += r_i - q_selected[q_cnt]
                    q_cnt += 1
                else:
                    return ans
            elif p_selected[p_cnt] < q_selected[q_cnt]:
                if p_selected[p_cnt] < r_i:
                    ans += r_i - p_selected[p_cnt]
                    p_cnt += 1
                else:
                    return ans
        elif q_cnt < Y and p_cnt >= X:
            if q_selected[q_cnt] < r_i:
                ans += r_i - q_selected[q_cnt]
                q_cnt += 1
            else:
                return ans
        elif p_cnt < X and q_cnt >= Y:
            if p_selected[p_cnt] < r_i:
                ans += r_i - p_selected[p_cnt]
                p_cnt += 1
            else:
                return ans

    return ans

ans = solve()

print(ans)
#!/usr/bin/env python3
# coding=utf-8

import sys

n = int(sys.stdin.readline().strip())

txy = [(0,0,0)]+[tuple(map(int, l.strip().split(" "))) for l in sys.stdin.readlines()]
check_txy = [abs(_x - _xp) + abs(_y -_ yp) <= _t - _tp and (_t + _x + _y) % 2 == 0 for (_t, _x, _y), (_tp, _xp, _yp) in zip(txy[1:], txy)]
if all(check_txy):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

#!/usr/bin/env python3
# coding=utf-8

import sys

n = int(sys.stdin.readline().strip())

txy = [tuple(map(int, l.strip().split(" "))) for l in sys.stdin.readlines()]
check_txy = [abs(_x) + abs(_y) <= _t and (_t + _x + _y) % 2 == 0 for (_t, _x, _y) in txy]
if all(check_txy):
    print("Yes")
else:
    print("No")
n = int(input())
a = []
b = []
if True:
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
kosuu = 1
mae = a[0]
for i in range(1,len(a)):
    if mae == a[i]:
        kosuu += 1
    else:
        mae = a[i]
        b.append(kosuu)
        kosuu = 1
b.append(kosuu)
ans = 0
for i in range(len(b)):
    for j in range(2,100):
        if b[i] < j*(j+1)//2:
            ans += j-1
            break
print(ans)

### FIXED CODE ###

n = int(input())
a = []
b = []
if n == 1:
    print(0)
    exit()
if True:
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
kosuu = 1
mae = a[0]
for i in range(1,len(a)):
    if mae == a[i]:
        kosuu += 1
    else:
        mae = a[i]
        b.append(kosuu)
        kosuu = 1
b.append(kosuu)
ans = 0
for i in range(len(b)):
    for j in range(2,100):
        if b[i] < j*(j+1)//2:
            ans += j-1
            break
print(ans)
N = int(input())
S = list(input())
if S == ['*'] * N or S == ['.'] * N:
    print(0)
    exit()

for i in range(N - 1, -1, -1):  # #->.
    if S[i] == '.':
        num1 = i
        break

for j in range(N):  # .->#
    if S[j] == '#':
        num2 = j
        break

ans1 = S[:num1].count('#')
ans2 = S[num2 + 1:].count('.')
print(min(ans1, ans2))


### FIXED CODE ###

N = int(input())
S = list(input())

w_cnt = [0]
w = 0
for s in S:
    if s == '.':
        w += 1
    w_cnt.append(w)

b_cnt = [0]
b = 0
for s in S[::-1]:
    if s == '#':
        b += 1
    b_cnt.append(b)
b_cnt.reverse()


ans = float('inf')
i = 0
for b, w in zip(b_cnt, w_cnt):
    ww, bb = i, N - i
    ans = min(ans, abs(b - bb) + abs(w - ww))
    i += 1
print(ans)
list = input().split()
ans = list[0] * list[1] * list[2]

if ans == 5*5*7:
  Print('YES')
else:
  Print('NO)


### FIXED CODE ###

list1 = input().split()
ans = int(list1[0]) * int(list1[1]) * int(list1[2])
 
if ans == 5*5*7:
  print('YES')
else:
  print('NO')
f = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
n = int(input())
k = []
for i in range(n):
    k.append(int(input()))

lis = []

lis.append(f)
lis.append(s)
lis.append(t)

ans = 0

for i in lis:
    c =0
    for n in range(len(i)):
        if i[n] in k:
            i[n] = 'X'
            c += 1
            if c == 3:
                ans +=1
                break

if f[0] == 'X' and s[0] == 'X' and t[0] == 'X':
    ans +=1
elif f[1] == 'X' and s[1] == 'X' and t[1] == 'X':
    ans += 1
elif f[2] == 'X' and s[2] == 'X' and t[2] == 'X':
    ans += 1
elif f[0] == 'X' and s[1] == 'X' and t[3] == 'X':
    ans += 1
elif f[3] == 'X' and s[2] == 'X' and t[1] == 'X':
    ans += 1
    
if ans < 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

f = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
n = int(input())
k = []
for i in range(n):
    k.append(int(input()))

lis = []

lis.append(f)
lis.append(s)
lis.append(t)

ans = 0

for i in lis:
    c =0
    for n in range(len(i)):
        if i[n] in k:
            i[n] = 'X'
            c += 1
            if c == 3:
                ans +=1
                break

if f[0] == 'X' and s[0] == 'X' and t[0] == 'X':
    ans +=1
elif f[1] == 'X' and s[1] == 'X' and t[1] == 'X':
    ans += 1
elif f[2] == 'X' and s[2] == 'X' and t[2] == 'X':
    ans += 1
elif f[0] == 'X' and s[1] == 'X' and t[2] == 'X':
    ans += 1
elif f[2] == 'X' and s[1] == 'X' and t[0] == 'X':
    ans += 1
    
if ans >= 1:
    print('Yes')
elif ans == 0:
    print('No')
N,M = map(int,input().split())
def f(N,M+1):
    if M%i ==0:
        return(M//i)
print(f(N,M+1))

### FIXED CODE ###

N,M = map(int,input().split())

m = M
f = {}
while m%2 == 0:
    f[2] = f.get(2,0) + 1
    m = m//2

k = 3
l = int(m**0.5)+1
while m != 1:
    if k > l:
        f[m] = f.get(m,0)+1
        break
    while m%k == 0:
        f[k] = f.get(k,0)+1
        m = m//k
    k += 2
C=[1]
for k in f:
    C_tmp = []
    for c in C:
        for i in range(f[k]):
            C_tmp.append(c*(k**(i+1)))
    C.extend(C_tmp)
ans_r = M
for c in C:
    if c>=N and c<ans_r:
        ans_r = c
print(M//ans_r)
c = [[],[],[]]
c[0] = [int(x) for x in input().split()]
c[1] = [int(x) for x in input().split()]
c[2] = [int(x) for x in input().split()]

ans = "Yes"
for i in range(3):
  for j in range(3):
  	if c[(i+1)%3][(j+1)%3] + c[(i+2)%3][(j+2)%3] != c[(i+2)%3][(j+1)%3] + c[(i+1)%3][(j+2)%3]
      ans = "No"	
      break
  if ans == "No":
    break
print(ans)

### FIXED CODE ###

c = [[],[],[]]
c[0] = [int(x) for x in input().split()]
c[1] = [int(x) for x in input().split()]
c[2] = [int(x) for x in input().split()]

ans = "Yes"
for i in range(3):
    for j in range(3):
        if c[(i+1)%3][(j+1)%3] + c[(i+2)%3][(j+2)%3] != c[(i+2)%3][(j+1)%3] + c[(i+1)%3][(j+2)%3]:
            ans = "No"
            break
    if ans == "No":
        break
print(ans)
wlist=[ i for i in input()]
klist=["k","e","y","e","n","c","e"]
a=0
b=0
while b<=6:
    if wlist[a]==klist[b]:
        a+=1
        b+=1
    else:
        a+=1
if b==7:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

wlist=[ i for i in input()]
klist=["k","e","y","e","n","c","e"]
a=[]
for i in range(len(wlist)-1):
    for j in range(i+1,len(wlist)):
        if wlist[0:i+1]+wlist[j:]==klist:
                a.append(1)
        else:
                a.append(0)
                
if 1 in a:
    print("YES")
else:
    print("NO")
# 二部探索で決めていく。dpですでに見られたかどうかは把握
from bisect import bisect_left
n,q  = map(int, input().split())
imos = [0] * n
roadworks = []
for i in range(n):
    s,t,x = map(int, input().split())
    roadworks.append((s,t,x))
roadworks.sort()

ds = [(int(input()),i) for i in range(q)]  
ds.sort()
ix = [d[1] for d in ds]
ds = [d[0] for d in ds]
xs = [-1]*(n+10)
for s,t,x in roadworks:
    # print(s-x,t-x)
    l = bisect_left(ds,s-x-0.5)
    r = bisect_left(ds,t-x-0.5)
    for i in range(l,r):
        if xs[i] != -1:continue
        xs[i] = x
    # print("index",l,r)

for i in range(q):
    print(xs[i])

### FIXED CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)
# 出力
# a, b = map(int, input().split())
a = int(input())
b = int(input())

# 処理&出力
if a / 3 >= 1 :
    print('Possible')
elif b / 3 >= 1:
    print('Possible')
elif (a + b) /3 >= 1:
    print('Possible')
else:
    print('Impossible')

### FIXED CODE ###


# 出力
a, b = map(int, input().split())

# 処理&出力
if (a + b) % 3 == 0:
    print('Possible')
elif a % 3  == 0:
    print('Possible')
elif b % 3 == 0:
    print('Possible')
else:
    print('Impossible')
N,Q=map(int,input().split())

S=input()

# 最初からNまでに何個ACがあったか
cnt=[0 for _ in range(N)]

prevA=False

for i in range(N):
	if S[i]=="C":
		if prev=="A":
			cnt[i]+=1
	if i!=0:
		cnt[i]+=cnt[i-1]
	prev = S[i]

for q in range(Q):
 	L,R=map(int,input().split())
 	ans = cnt[R-1]-cnt[L-1]
 	print(ans)


### FIXED CODE ###

N,Q=map(int,input().split())

S=input()

# 最初からNまでに何個ACがあったか
cnt=[0 for _ in range(N)]

prev=""

for i in range(N):
	if S[i]=="C":
		if prev=="A":
			cnt[i]+=1
	if i!=0:
		cnt[i]+=cnt[i-1]
	prev = S[i]

for q in range(Q):
 	L,R=map(int,input().split())
 	ans = cnt[R-1]-cnt[L-1]
 	print(ans)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
uni = UnionFind(n)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
t = set([])
for i in range(m):
    p = uni.find(i)
    t.add(p)
print(len(t))

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
uni = UnionFind(n-1)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
t = set([])
for i in range(n):
    p = uni.find(i)
    t.add(p)
print(len(t))
N = int(input())
a = [ ]
for i in range(1:10):
    for j in range(i:10):
        b = i*j
        a.append(b)
if list.count(N) == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
a = [ ]
for i in range(1,10):
    for j in range(i,10):
        b = i*j
        a.append(b)
if a.count(N) == 0:
    print('No')
else:
    print('Yes')
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10**5 + 100
dp = [INF] * (MAX_V + 1)
dp[0] = 0

for wi, vi in wv:
	for sum_v in reversed(range(vi, MAX_V+1)):
        dp[sum_v] = min(dp[sum_v - vi] + wi, dp[sum_v])
#print(dp)
ans = 0
for i in range(MAX_V, -1, -1):
    if dp[i] <= w:
        print(i)
        exit()
#print(ans)


### FIXED CODE ###

import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

INF = 10**9 + 100
MAX_V = 10 ** 6

dp = np.full((n+1, MAX_V), INF, np.int64)
dp[0][0] = 0

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.minimum(dp[i][vi:], dp[i][:-vi] + wi, out=dp[i+1][vi:])

ans = np.where(dp[n] <= w)[0][-1]
print(ans)
import sys
sys.setrecursionlimit(1000000)
N, K = map(int, input().split())
S = list(input())
X = []
cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        X.append(cnt)
        cnt = 0
    cnt += 1
    if i == N-1:
        X.append(cnt)

l = len(X)
if S[0] == '0' and (l+1)//2 <= k:
    print(N)
    exit()
if S[0] == '1' and l//2 <= k:
    print(N)
    exit()

ans = []
if S[0] == '1': 
    sum0 = sum(X[0:2*K+1])
    ans.append(sum0)
    i = 1
    while 2*K+2*i-1 < len(X):
        ans.append(ans[i-1] + X[2*K+2*i-1] + X[2*K+2*i] - X[2*i] - X[2*i-1])
        i += 1
else:
    sum0 = sum(X[0:2*K])
    ans.append(sum0)
    i = 1
    while 2*K+2*i <= len(X):
        if i == 1:
            ans.append(ans[i-1] + X[2*K+2*i-2] + X[2*K+2*i-1] - X[i-1])
            i += 1
        else:
            ans.append(ans[i-1] + X[2*K+2*i-2] + X[2*K+2*i-1] - X[2*i] - X[2*i-1])
            i += 1
print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
X = []
cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        X.append(cnt)
        cnt = 0
    cnt += 1
    if i == N-1:
        X.append(cnt)
l = len(X)

if S[0] == '0' and (l+1)//2 <= K:
    print(N)
    exit()
if S[0] ==  '1' and l//2 <= K:
    print(N)
    exit()

ans = 0
result = 0
if S[0] == '0':
    for j in range(2*K):
        result += X[j]
    ans = result
    for j in range(2*K, l):
        if j == 2*K:
            result -= X[0]
        elif j%2 == 0:
            result = result - X[j-2*K] - X[j-2*K-1]
        result += X[j]
        ans = max(ans,result)
else:
    for j in range(2*K+1):
        result += X[j]
    ans = result
    for j in range(2*K+1, l):
        if j%2 == 1:
            result = result - X[j-2*K-1] - X[j -2*K]
        result += X[j]
        ans = max(ans, result)
print(ans)
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in reversed(range(1, n+1)):
    if A[i] <= B[i-1]:
        ans += A[i]
        B[i-1] -= A[i]
        if A[i-1] >= B[i-1]:
            ans += B[i-1]
            A[i-1] -= B[i-1]
        else:
            ans += A[i-1]
            A[i-1] = 0
    else:
        ans += B[i]
        B[i-1] = 0
print(ans)

### FIXED CODE ###

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

ans = 0

for i in reversed(range(n+1)):
  if i == n:
    temp = min(a[i], b[i-1])
    ans += temp
    b[i-1] -= temp
  elif i == 0:
    ans += min(a[i], b[i])
  else:
    temp1 = min(a[i], b[i])
    ans += temp1
    a[i] -= temp1
    temp2 = min(a[i], b[i-1])
    ans += temp2
    b[i-1] -= temp2
print(ans)
import numpy as np

MOD = 10**9+7

D,T,E = input().split()
n= int(D)
print(5)

### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
x=input()
print(f"{x[0]*x[1}} {(x[0]+x[1])*2}")

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,a*2+b*2)