Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9+10)

mod = 10**9+7

def dfs(x,y):
    if not(0<=x<H) or not(0<=y<W):
        return
    if  maze[x][y]=="#":
        return
    
    if x==H-1 and y==W-1:
        return
        
    dh = [1,0]
    dw = [0,1]
    
    for i,j in zip(dh,dw):
        if (0<=x+i<H) and (0<=y+j<W):
            if maze[x+i][y+j]!="#":
                dp[x+i][y+j] += 1
                dp[x+i][y+j] %= mod
        dfs(x+i,y+j)

H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]

dp = [[0]*W for _ in range(H)]
dp[0][0]=1

dfs(0,0)
print(dp[H-1][W-1])

### FIXED CODE ###

mod = 10**9+7
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
dp = [[0]*W for _ in range(H)]
dp[0][0]=1

for i in range(H):
    for j in range(W):
        if i+1<H and maze[i+1][j]==".":
            dp[i+1][j] += dp[i][j]%mod
        if j+1<W and maze[i][j+1]==".":
            dp[i][j+1] += dp[i][j]%mod
            
print(dp[H-1][W-1]%mod)
### BUGGY CODE ###

import math

a, b, n = map(int, input().split())
s = 0
for i in range(1, n + 1):
    s = max(s, int(a * i / b) - a * int(i / b))

print(s)

### FIXED CODE ###

import math

a, b, n = map(int, input().split())
x = b - 1
if n < x:
    x = n

ans = int(a * x / b) - a * int(x / b)

print(ans)
### BUGGY CODE ###

def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = [[0 for i in range(N)]for j in range(N)]
    result = [0]*(N-1)
    record = [0]
    count = N-1
    in1 = 0
    in2 = 0
    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        if in1-1 < in2-1:
            aisle[in1-1][in2-1] = 1
        else:
            aisle[in2-1][in1-1] = 1

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        for i in range(N-1):
            if aisle[pop1][i+1] == 1 and result[i] == 0:
                result[i] = pop1+1
                record.append(i+1)
                count = count - 1
            if aisle[i+1][pop1] == 1 and result[i] == 0:
                result[i] = pop1+1
                record.append(i+1)
                count = count - 1

    if count == 0:
        print("Yes")
    else:
        print("No")
    for i in range(len(result)):
        print(result[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = {}
    result = [0]*(N-1)
    record = [1]
    count = N-1
    in1 = 0
    in2 = 0

    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        aisle.setdefault(in1,[]).append(in2)
        aisle.setdefault(in2,[]).append(in1)

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        if pop1 in aisle:
            for i in aisle[pop1]:
                if result[i-2] == 0 and i >= 2:
                    result[i-2] = pop1
                    record.append(i)
                    count = count -1

    if count == 0:
        print("Yes")
        for i in range(len(result)):
            print(result[i])
    else:
        print("No")


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import defaultdict
N,P=map(int,input().split())
A=defaultdict(int)
i=2
ans=1
while P!=1:
    if P%i==0:
        A[i]+=1
        P//=i
    else:
        i+=1
for key,value in A.items():
    if value>=N:
        ans*=key**(value//N)
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
 
def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
	if m>1 : pf[m]=1
	return pf
 
ans = 1
for i, j in pfact(p).items():
	ans *= i**(j//n)
print(ans)
### BUGGY CODE ###

N,x = list(map(int,input().split()))
a=list(map(int,input().split()))

eat=0

if a[0]>x:
  eat+=a[0]-x+1
  a[0]=x-1
  
for i in range(N-1):
  while a[i]+a[i+1]>x:
    a[i+1]-=1
    eat+=1
    
print(eat)

### FIXED CODE ###

N,x = list(map(int,input().split()))
a=list(map(int,input().split()))

eat=0

if a[0]>x:
  eat+=a[0]-x
  a[0]=x

if a[N-1]>x:
  eat+=a[N-1]-x
  a[N-1]=x
  
for i in range(N-1):
  if a[i]+a[i+1]>x:
    eat+=a[i+1]-x+a[i]
    a[i+1]=x-a[i]
    
print(eat)
### BUGGY CODE ###

import numpy as np
from numba import *

@njit('i8(i8,i8[:],i8[:])', cache=True)
def solve(x,nums, count):
    for i in range(2,x+1):
        count[np.arange(i,x+1,i)] += 1
    count[0] = 0
    return int(np.sum(nums*count))

if __name__== "__main__":
    x = int(input())
    nums = np.arange(x + 1, dtype=np.int64)
    count = np.ones(x + 1, dtype=np.int64)
    print(solve(x,nums,count))

### FIXED CODE ###

import numpy as np
from numba import *

@njit('i8(i8,i8[:])', cache=True)
def solve(x,count):
    for i in range(2,x+1):
        for j in range(i,x+1,i):
            count[j] += 1
    return int(np.sum(np.arange(x+1)*count))

if __name__== "__main__":
    x = int(input())
    count = np.ones(x + 1, dtype=np.int64)
    print(solve(x,count))
### BUGGY CODE ###

mod = 10**9+7
S = input()

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    s = S[len(S)-i-1]
    if s == '?':
        c = range(10)
    else:
        c = [int(s)]

    for d in c:
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

    for k in range(13):
        dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5])


### FIXED CODE ###

mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 13] += dp[i][j]

    for k in range(13):
        dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5])
### BUGGY CODE ###

s=list(input())   
adj=-1
op=0

while(adj==-1):
    adj=0
    for i in range(1,len(s)):
        if(s[i]!=s[i-1]):
            adj=-1
            del(s[i], s[i-1])
            op+=2
            break
         
print(op)


### FIXED CODE ###

s = input()
print(2*(min(s.count("0"), s.count("1"))))
### BUGGY CODE ###

# seishin.py
N = int(input())
*A, = map(int, input().split())

def solve(x):
    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
    c = 0; d = 10**18
    for a in A:
        if x <= a:
            c += 1
        else:
            c -= 1
        d = min(c, d)
    res = N*(N+1)//2
    c = -d+1
    for a in A:
        res -= get(c)
        if x <= a:
            c += 1
        else:
            c -= 1
        add(c, 1)
    return res <= N*(N+1)//4

left = min(A); right = max(A)+1
while left+1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)

### FIXED CODE ###

# seishin.py
N = int(input())
*A, = map(int, input().split())

def solve(x):
    data = [0]*(N+1)
    def add(k, x):
        while k <= N:
            data[k] += x
            k += k & -k
    def get(k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
    c = 0; d = 10**18
    for a in A:
        if x <= a:
            c += 1
        else:
            c -= 1
        d = min(c, d)
    res = N*(N+1)//2
    c = -d+1
    for a in A:
        res -= get(c)
        if x <= a:
            c += 1
        else:
            c -= 1
        add(c, 1)
    return res <= N*(N+1)//4

left = min(A); right = max(A)+1
while left+1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)
### BUGGY CODE ###

S=input()
T=input()

s=len(S)
t=len(T)
#DPテーブル作成
dp=[['']*(t+1) for _ in range(s+1)]

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + S[i]
        else:
            dp[i+1][j+1] =  max([ dp[i+1][j] , dp[i][j+1] ],key=len)
print(dp[s][t])

### FIXED CODE ###

S=input()
T=input()

s,t=len(S),len(T)
#DPテーブル作成
dp=[[0]*(t+1) for _ in range(s+1)]

for i in range(s):
    for j in range(t):
        if S[i] ==T[j]:
            dp[i+1][j+1] =dp[i][j] + 1
        else:
            dp[i+1][j+1] =  max([ dp[i+1][j] , dp[i][j+1] ])
# print(*dp,sep="\n")

res = ''
while s != 0 and t != 0:
    if dp[s][t] == dp[s-1][t]:
        s -= 1
    elif dp[s][t] == dp[s][t-1]:
        t -= 1
    else:
        s -= 1
        t -= 1
        res = S[s] + res

# print(dp[s][t])
print(res)
### BUGGY CODE ###

import itertools
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    cnt=0
    for i in itertools.combinations(range(101),n):
        if len(set(i))==n and sum(i)==s:
            cnt+=1
        if i[0]>=s:break
    print cnt

### FIXED CODE ###

dp=[[0]*1001 for i in range(11)]
dp[0][0]=1
for i in range(101):
    for j in range(10)[::-1]:
        for k in range(1001-i):
            dp[j+1][k+i]+=dp[j][k]
while True:
    n,s=map(int,raw_input().split())
    if n==s==0:break
    print dp[n][s]
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
xhl = [ [z[0], z[1]] for z in xh ]
cnt = 0
i = 0
while i<n:
    x = xhl[i][0]
    h = xhl[i][1]
    if h<=0:
        i += 1
        continue
    j = i
    while j<n-1 and xhl[j+1][0]<=x+2*d:
        j += 1
    for k in range(i,j+1):
        xhl[k][1] -= h
    cnt += h
print(cnt)


### FIXED CODE ###

from sys import stdout
from collections import deque
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
q = deque([])
ad = 0
for i in range(n):
    h = xh[i][1]
    x = xh[i][0]
    while len(q)>0 and q[0][0]<x:
        z = q.popleft()
        ad -= z[1]
    h -= ad
    if h<=0:
        continue
    cnt += h
    ad += h
    q.append((x+2*d,h))
print(cnt)
### BUGGY CODE ###

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

ans = 0

for a in range(0, k+1):
    for b in range(0, k+1):
        for c in range(0, k+1):
            if a+b+c == s:
                ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0

for x in range(0, k+1):
    for y in range(0, k+1):
        z = s - x - y
        if 0 <= z and z <= k:
            ans += 1

print(ans)
### BUGGY CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    

    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
            
      
        
        



### FIXED CODE ###

N, M, R = map(int, input().split())
R_LIST = list(map(int, input().split()))
ABC = []
for _ in range(M):
    a,b,c = map(int, input().split())
    ABC.append((a,b,c))
    
    
edges = ABC[:]


def warshall_floyd(d, n):
    # d: グラフ二次元リスト
    # n: 頂点数 (0始まり)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

# グラフ無効グラフ化
graph = [[float("inf") for i in range(N+1)] for i in range(N+1)] 
for x,y,z in edges:
    graph[x][y] = z
    graph[y][x] = z
for i in range(N+1):
    graph[i][i] = 0 #自身のところに行くコストは０

#最短経路
shortest =  warshall_floyd(graph, N+1)
    
# 順列全探索
import sys
INT_MAX = sys.maxsize # 9223372036854775807
ans = INT_MAX

import queue

rest = set(R_LIST[:])

import copy  
def dfs(cost,pre,rest):
    if len(rest) == 0:
        return cost
    
    ret = INT_MAX
    for r in rest:
        if pre == None:
            next_cost = 0
        else:
            next_cost = cost + shortest[pre][r]
        next_rest = copy.copy(rest)
        next_rest.remove(r)
        
        tmp_ret = dfs(next_cost, r, next_rest)
        ret = min(ret, tmp_ret)
        
    return ret
        
    

print(dfs(0, None, rest))
### BUGGY CODE ###

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


def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        if S[i+n:].find(now) != -1:
            return True
    return False


left = 0
right = N//2+2

while right - left > 1:
    mid = left + (right-left)//2
    if not isok(mid):
        right = mid
    else:
        left = mid

print(left)


### FIXED CODE ###

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


r = 1
ans = 0
for l in range(N):

    while True:
        #print(S.rfind(S[l:r+1]), S[l:r+1], l, r)

        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
INF = 10**9

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {v: i for i, v in enumerate(alph)}
dp = [INF]*(n+1)
dp[0] = 0

for i in range(n):
    tmp = 0
    for j in range(i+1)[::-1]:
        tmp ^= 1 << to_int[s[j]]
        if bin(tmp).count("1") <= 1:
            dp[i+1] = min(dp[j] + 1, dp[i+1])
print(dp[-1])

### FIXED CODE ###

s = input()
n = len(s)
INF = 10**9

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {v: i for i, v in enumerate(alph)}
dp = {}
all_state = 0

for i in range(n):
    all_state ^= 1 << to_int[s[i]]
    if all_state not in dp:
        dp[all_state] = i + 1
    for j in range(26):
        bit = all_state ^ (1 << j)
        if bit in dp:
            dp[all_state] = min(dp[bit] + 1, dp[all_state])
    if bin(all_state).count("1") <= 1:
        dp[all_state] = 1
print(dp[all_state])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N=int(input())
a=list(map(int,input().split()))
fl=1
def absX(n):
	ab=abs(X-n)
	if ab==0:
		ab=1
	return ab
for i in range(min(a),max(a)+1):
	X=i
	fl_=list(map(absX,a)).count(1)
	if fl_>fl:
		fl=fl_
print(fl)

### FIXED CODE ###

from collections import*
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
a=Counter(a)
cnt=1
for i in range(min(a),max(a)+1):
	cnt_=a[i-1]+a[i]+a[i+1]
	if cnt_>cnt:cnt=cnt_
print(cnt)
### BUGGY CODE ###

n=int(input())
alis=[int(input()) for i in range(n)]
anslis=[0]*n
if alis.count(max(alis))>=2:
	for i in range(n):
		print(max(alis))
else:
	for i in range(n):
		if i!=alis.index(max(alis)):
			print(max(alis))
		else:
			print(sorted(alis)[-2])

### FIXED CODE ###

n=int(input())
alis=[int(input()) for i in range(n)]
anslis=[max(alis)]*n
if alis.count(max(alis))==1:
	anslis[alis.index(max(alis))]=sorted(alis)[-2]
for i in range(n):
	print(anslis[i])
### BUGGY CODE ###

import math
N=int(input())
for i in range(math.ceil(N**0.5),N+1):
 if N%i==0:print(len(str(i)));break


### FIXED CODE ###

N=int(input())
print(min(len(str(N//i))for i in range(1,int(N**.5)+1)if N%i<1))
### BUGGY CODE ###

from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

a = [[True]*w for _ in range(h)]

while s:
    q = s.popleft()
    
    a[q[0]][q[1]] = False
    ans = q[2]
    
    if q[0]>0 and a[q[0]-1][q[1]]:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1 and a[q[0]+1][q[1]]:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0 and a[q[0]][q[1]-1]:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1 and a[q[0]][q[1]+1]:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N, K, Q = map(int, input().split())
import sys
input = sys.stdin.readline
A = [K] * N
def calc(n):
  return n-1
for i in range(Q):
  M = int(input().rstrip())
  A = list(map(calc, A))
  A[M-1] += 1
for k in A:
  if k <= 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N, K, Q = map(int, input().split())
import sys
input = sys.stdin.readline
A = [0] * N
for i in range(Q):
  s = int(input().rstrip())
  A[s-1] += 1
for k in A:
  if K - (Q - k) >= 1:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap=[]

#print(board)
for i in range(0,N):
    a, b = input().split()
    a = int(a)
    b = int(b)
    al = max(a-1, 2)
    au = min(a+2, H)
    bl = max(b-1, 2)
    bu = min(b+2, W)

    for j in range(al, au):
        for k in range(bl, bu):
            rectmap.append([j-1, k-1])
##    for j in range(a-1, a+2):
##        for k in range(b-1, b+2):
##            if j>1 and j<H and k>1 and k<W:
##                rectmap.append([j-1, k-1])
#print(rectmap)
rectmap.sort()
while len(rectmap)!=0 :
    c = rectmap.count(rectmap[0])
    del rectmap[:c]
    count[c]+=1
    count[0]-=1
for i in range(0, 10):
    print(count[i])    
#print(H,W,N)
#print(ab)


### FIXED CODE ###

import math

H, W, N = map(int, input().split())
count = [0]*10
count[0] = (H-2)*(W-2)
rectmap={}

#print(board)
for i in range(0,N):
    a, b = input().split()
    a = int(a)
    b = int(b)
    ab = (a, b)
    al = max(a-1, 2)
    au = min(a+2, H)
    bl = max(b-1, 2)
    bu = min(b+2, W)

    for j in range(al, au):
        for k in range(bl, bu):
            if (j,k) in rectmap:
                rectmap[(j,k)] +=1
            else:
                rectmap[(j,k)] = 1
#            print(rectmap)
##    for j in range(a-1, a+2):
##        for k in range(b-1, b+2):
##            if j>1 and j<H and k>1 and k<W:
##                rectmap.append([j-1, k-1])
#print(rectmap)
for i in rectmap.values():
    count[i]+=1
    count[0]-=1
for c in count:
    print(c)
#print(H,W,N)
#print(ab)
### BUGGY CODE ###

nums = list(map(int, input().split()))
N, K = nums[0], nums[1]
S = input()

first_one = S[0] == '1'
cnts = []
cnt = 1
for i, e in enumerate(S):
    if i == 0:
        pass
    else:
        if e != S[i-1]:
            cnts.append(cnt)
            cnt = 1
        else:
            cnt += 1
cnts.append(cnt)


zero_obj = []
for i, c in enumerate(cnts):
    if first_one:
        if i % 2 == 1:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))
    else:
        if i % 2 == 0:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))

if len(zero_obj) <= K:
    print(len(S))
else:
    m = -1
    for i in range(len(zero_obj) - K + 1):
        tmp = zero_obj[i][0]
        for j in range(K):
            tmp += zero_obj[i+j][1] + zero_obj[i+j][2]
        if tmp > m:
            m = tmp
    print(m)


### FIXED CODE ###

nums = list(map(int, input().split()))
N, K = nums[0], nums[1]
S = input()

first_one = S[0] == '1'
cnts = []
cnt = 1
for i, e in enumerate(S):
    if i == 0:
        pass
    else:
        if e != S[i-1]:
            cnts.append(cnt)
            cnt = 1
        else:
            cnt += 1
cnts.append(cnt)


zero_obj = []
for i, c in enumerate(cnts):
    if first_one:
        if i % 2 == 1:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))
    else:
        if i % 2 == 0:
            left = 0
            if i - 1 >= 0:
                left = cnts[i-1]
            right = 0
            if i + 1 < len(cnts):
                right = cnts[i+1]
            zero_obj.append((left, c, right))

if len(zero_obj) <= K:
    print(len(S))
else:
    m = -1
    tmp = zero_obj[0][0]
    for i in range(K):
        tmp += zero_obj[i][1] + zero_obj[i][2]
    m = tmp
    for i in range(len(zero_obj) - K):
        tmp -= zero_obj[i][0] + zero_obj[i][1]
        tmp += zero_obj[i+K][1] + zero_obj[i+K][2]
        if tmp > m:
            m = tmp
    print(m)