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

n=int(input())
aa=list(map(int,input().split()))
bb=list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(1,n+1):
    mx=i
    for a,b in zip(aa,bb):
        if i>=a:
            tmp=dp[i-a]+b
            if tmp>mx:
                mx=tmp
        dp[i]=mx
n=dp[-1]
dp=[0]*(n+1)
for i in range(1,n+1):
    mx=i
    for a,b in zip(aa,bb):
        if i>=b:
            tmp=dp[i-b]+a
            if tmp>mx:
                mx=tmp
        dp[i]=mx
print(dp[-1])


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if len(rate)==1:
        a,b=rate[0]
        p,m=divmod(dk,a)
        return p*b+m
    if len(rate)==2:
        a0,b0=rate[0]
        a1,b1=rate[1]
        if b0/a0<b1/a1:
            a0,b0,a1,b1=a1,b1,a0,b0
        p0,m=divmod(dk,a0)
        re=b0*p0
        p1,m=divmod(m,a1)
        re+=b1*p1+m
        while p0>0 and m>0:
            p0-=1
            m+=a0
            p2,m=divmod(m,a1)
            p1+=p2
            tmp=p0*b0+p1*b1+m
            if tmp>re:
                re=tmp
        return re
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp = [-1] * (n + 1)
n = don(n, atob, amin)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))
### BUGGY CODE ###

n,m=map(int,input().split())
d=[ list(map(int,input().split()))  for i in range(n)]
dp=[0]*(m+2)

for i in range(n):  #商品を一つずつ見ていく。
  for j in range(m+1,d[i][0],-1): #w~(限界-w)までのdpの箱に入れていく。(例)w,m=3,8なら3~5
    dp[j]=max(dp[j-d[i][0]]+d[i][1],dp[j]) #d[i][0]=w d[i][1]=v
    
print(dp[m+1])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)

    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import math

def eratosthenes(l, r):
    prime_list = [i for i in (2, 3, 5) if i <= r]

    candidates = [i for i in range(2, r+1) if i % 2 and i % 3 and i % 5]
    while len(candidates):
        prime_list.append(candidates[0])
        candidates = [i for i in candidates[1:] if i % candidates[0]]
    return [i for i in prime_list if i >= l]

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def is_prime(n):
    return len(prime_decomposition(n)) == 1

def similer_number_2017(l, r):
    similar_numbers = []
    for p in eratosthenes(l, r):
        if is_prime(int((p+1)/2)):
            similar_numbers.append(p)
    return similar_numbers
    

Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

for l, r in query:
    print len(similer_number_2017(l, r))




### FIXED CODE ###

Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

composite_number = [False] * (100001)
for i in range(2, 100001):
    if not composite_number[i]:
        for j in range(i+i, 100001, i):
            composite_number[j] = True
    
similar_number = [0] * 100001
for i in range(3, 100001, 2):
    if not composite_number[i] and not composite_number[(i+1)/2]:
        similar_number[i] += 1

for i in range(3, 100001):
    similar_number[i] += similar_number[i-1]

for l, r in query:
    print similar_number[r] - similar_number[l-1]
### BUGGY CODE ###

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(q):
    c = 0
    while q:
        q, r = divmod(q, 2)
        c += r
    return c

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)

### FIXED CODE ###

n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(n):
    return bin(n).count('1')

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print(0)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print(dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1)
        else:
            print(dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "B":
        return 2
    else:
        return 3

def solve(s: str):

    res = 0

    s = [ conv2num(c) for c in s ]
    i = 0
    endi = len(s) - 2
    while i < endi:
        if s[i] == 1 and s[i+1] == 2 and s[i+2] == 3:
            ai = i
            for j in range(i-1,-1,-1):
                if s[j] == 1 and j >=0 :
                    ai = j 
                else:
                    break
            s[ai]   = 2
            s[ai+1] = 3
            s[ai+2] = 1
            res += 1

            st = ai+3
            ed = i +3
            if st != ed:
                for k in range(st,ed):
                    s[k] = 1
                    res += 1
            i += 1
        i += 1

    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "D":
        return 2
    elif c == "B":
        return 3
    else:
        return 4

def solve(s: str):

    res = 0
    s = s.replace("BC","D")
    s = [ conv2num(c) for c in s ]

    acnt = 0
    for i,c in enumerate(s):
        if c == 1:
            acnt += 1
        elif c == 2:
            res += acnt
        else:
            acnt = 0


    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

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

while True:
    n = int(raw_input())
    if n == 0:
        break
    a = map(int, raw_input().split())
    b = list(set(a))
    flag = 0
    for i in b:
        if a.count(i) > n/2.0:
            ans = i
            flag = 1
            break
    print ans if flag == 1 else "NO COLOR"

### FIXED CODE ###

while 1:
    n = input()
    if n == 0: break
    A = map(int,raw_input().split())
    A.sort()
    c,l = A[0],0
    for i in A:
        if i == c:
            l += 1
            if l > n/2:
                print c
                break
        else:
            c = i
            l = 1
    else:
        print "NO COLOR"
### BUGGY CODE ###

from collections import deque

h,w = list(map(int,input().split()))
par = [[x for x in input()] for _ in range(h)]
que = deque([])
for i in range(h):
  for j in range(w):
    if par[i][j] == '#':
      que.append([i,j])

m = par.copy()

dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(que):
  next_que = deque([])
  while que:
    cur = que.popleft()
    
    for i in range(4):
      nh = cur[0] + dh[i]
      nw = cur[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
        m[nh][nw] = '#'
        next_que.append([nh,nw])
        
  return next_que


cnt = 0
while que:
  cnt += 1
  que = bfs(que)

print(cnt-1)

### FIXED CODE ###

from collections import deque

h,w = list(map(int,input().split()))
m = [[x for x in input()] for _ in range(h)]
next_que = deque([])
for i in range(h):
  for j in range(w):
    if m[i][j] == '#':
      next_que.append([i,j])


dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(next_que):
  cnt = -1
  while next_que:
    cnt += 1
    que = list(next_que)
    next_que = deque([])
    for cur in que:
      #cur = que.popleft()
      for i in range(4):
        nh = cur[0] + dh[i]
        nw = cur[1] + dw[i]
        
        if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
          m[nh][nw] = '#'
          next_que.append([nh,nw])
  
  return cnt



cnt = bfs(next_que) 

print(cnt)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]

def dfs(i,w):
    if (i,w) in dic: return dic[(i,w)]
    if i == N or w <=0: return 0
    ma = 0 
    res1 = res2 = 0 
    if A[i][0] <=w:
        res1 = dfs(i + 1,w - A[i][0]) + A[i][1]
    res2 = dfs(i + 1,w)
    ma = max(res1,res2)
    dic[(i,w)] = ma
    return ma
dic = {}
res = dfs(0,W)
print(res)

### FIXED CODE ###

import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for _ in range(W+1) ] for _ in range(N + 1)] 

for i in range(1,N + 1): 
    for j in range(W + 1): 
        if j - A[i-1][0] >= 0:
            res1 = dp[i - 1][j - A[i-1][0]] + A[i - 1][1]
            res2 = dp[i - 1][j]
            dp[i][j] = max(res1,res2)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print(max(dp[N]))
### BUGGY CODE ###

n,q=map(int,input().split())
m,p=[0],[0]
for _ in[0]*n:
 s,k=input().split()
 m+=[s]
 p+=[int(k)]
b=list(range(n+1))
t=0
while sum(b):
 for i in b:
  if p[i]>q:p[i]-=q;t+=q
  elif m[i]:b[i]=0;t+=p[i];print(m[i],t)


### FIXED CODE ###

import sys
from collections import deque
def m():
 s=sys.stdin.readlines()
 q=int(s[0].split()[1])
 f=lambda x,y:(x,int(y))
 d=deque(f(*e.split())for e in s[1:])
 t,a=0,[]
 while d:
  k,v=d.popleft()
  if v>q:v-=q;t+=q;d.append([k,v])
  else:t+=v;a+=[f'{k} {t}']
 print('\n'.join(a))
if'__main__'==__name__:m()
### BUGGY CODE ###

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

a,x=MI()
size=[0 for i in range(a+1)]
size[0]=1
for i in range(a):
    size[i+1]=size[i]*2+3
#print(size)
#print(size[1])
def porb(k,n):
    if k==1 and n==0:
        return "p"
    elif k==size[n] or k==1:
        return "b"
    elif k>(size[n]+1)//2:
        return porb(k-(size[n]+1)//2,n-1)
    elif k==(size[n]+1)//2:
        return "p"
    else:
        return porb(k-1,n-1)
ans=0
#print(porb(x,a))
for i in range(1,x+1):
    #print(i)
    #print(porb(i,a))
    if porb(i,a)=="p":
        ans+=1

print(ans)

### FIXED CODE ###

#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

a,x=MI()
size=[0 for i in range(a+1)]
size[0]=1
for i in range(a):
    size[i+1]=size[i]*2+3
#print(size)
#print(size[1])
patty=[0 for i in range(a+1)]
patty[0]=1
for i in range(a):
    patty[i+1]=2*patty[i]+1

def porb(k,n):
    if k==1 and n==0:
        return 1
    elif k==1:
        return 0
    elif k==size[n]:
        return patty[n]
    elif k>(size[n]+1)//2:
        return patty[n-1]+1+porb(k-(size[n]+1)//2,n-1)
    elif k==(size[n]+1)//2:
        return patty[n-1]+1
    else:
        return porb(k-1,n-1)

print(porb(x,a))
### BUGGY CODE ###

n = int(input())
s = input()

tmin = 0
for i in range(0, n):
    t = 0
    for j in range(0, n):
        if j == i:
            continue
        sd = "E" if j < i else "W"
        if s[j] != sd:
             t += 1
    if t < tmin or i == 0:
         tmin = t
print(tmin)

### FIXED CODE ###

n = int(input())
s = input()

e = [0 for i in range(n)]
w = [0 for i in range(n)]
for i in range(0, n - 1):
    et = e[i - 1] if i != 0 else 0
    et += 1 if s[i] != "E" else 0
    e[i] = et
    wt = w[(n - 1 - i) + 1] if i != 0 else 0
    wt += 1 if s[n - 1 - i] != "W" else 0
    w[n - 1 - i] = wt
# import pdb; pdb.set_trace()
tmin = 0
for i in range(0, n):
    t = 0
    t += e[i - 1] if i != 0 else 0
    t += w[i + 1] if i != (n - 1) else 0
    if t < tmin or i == 0:
        tmin = t 
print(tmin)
### BUGGY CODE ###

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

# print(s)

result=0
for i in range(Q):
	l, r = map(int,input().split())
	for i in range(l-1,r-1):
		if s[i]== "A" and s[i+1]== "C":
 			result = result+1
	print(result)
	result=0


### FIXED CODE ###

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

count=[]
num=0
count.append(num)
for i in range(len(s)-1):
	if s[i] == "A" and s[i+1] == "C":
		num=num+1
		count.append(num)
	else:
		count.append(num)

for i in range(Q):
	l, r = map(int,input().split())
	print(count[r-1]-count[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    #ans += A[s]*sm

print(ans%mod)

### FIXED CODE ###

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

k = 1000000007

sm = sum(A)

ans = 0
for s in range(len(A)-1):
    #ans += A[s]*sum(A[s+1:])
    sm -= A[s]
    ans += A[s]*sm

if ans>1000000007:
    print(ans%k)
else:
    print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for _ in range(int(input())):
    B,C=map(int,input().split())
    A=[C if i==B else i for i in A]
    print(sum(A))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
s=sum(A)
num=[0]*100001
for i in A:
    num[i]+=1
for _ in range(int(input())):
    B,C=map(int,input().split())
    s+=(C-B)*num[B]
    num[C]+=num[B]
    num[B]=0
    print(s)
### BUGGY CODE ###

#<D>
N = int(input())
num = [n for n in range(1, N + 1)]
print(sum(num) - N)
    

### FIXED CODE ###

N = int(input())
print((N - 1) * N // 2)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
import numpy as np
left = []
a = []
for i in range(N):
  if (i == 0 or i == 1):
      a.append(0.5)
  else:
    a.append(0)
a = np.array(a)
for i in range(N):
  left.append(np.roll(a, i))
left = np.array(left)
from numpy.linalg import solve
answer = solve(left, A)
answer = list(map(int, answer))
print(*answer)

### FIXED CODE ###

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

X = []
X.append(sum(A)-2*sum(A[2*i+1] for i in range(N//2)))
for i in range(N-1):
  X.append(2*A[i]-X[-1])
print(*X)
### BUGGY CODE ###

from collections import Counter
N=int(input())
A=list(map(int,input().split()))
C=list(Counter(A).values())
C.sort()

def ans(C,k):
    if C==[]:
        return 0
    elif sum(C)>=k*C[-1]:
        return sum(C)//k
    else:
        return ans(C[:-1],k-1)


for k in range(1,N+1):
    print(ans(C,k))

### FIXED CODE ###

from collections import Counter
import bisect
N=int(input())
A=list(map(int,input().split()))
C=list(Counter(A).values())
C.sort()
L=len(C)

# Cのうちx以上のものの個数D[x]を計算(x=0,...,N)
D=[L-bisect.bisect_left(C,x) for x in range(N+1)]
S=[0]
for n in range(1,N+1):
    S.append(S[-1]+D[n])

# T[x]=S[x]/x(x=1,...,N)としてKをbisect_rightで挿入した時のindexが答え
T=[x/S[x] for x in range(1,N+1)]
for K in range(1,N+1):
    print(bisect.bisect_right(T,1/K))
### BUGGY CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
res=[0]
f=0
for j in range(1,h+1):
    ff=[]
    for i in range(n):

        if 0>=j-M[i][0]:
            ind=0
        else:
            ind=j-M[i][0]
        kari=res[ind]+M[i][1]
        
        ff.append(kari)
    res.append(min(ff))
print(res[-1])

### FIXED CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
res=[0]
f=0
for j in range(1,h+1):
    
    i=0
    if 0>=j-M[i][0]:
        ind=0
    else:
        ind=j-M[i][0]
    ff=res[ind]+M[i][1]
    
    for i in range(1,n):
        if 0>=j-M[i][0]:
            ind=0
        else:
            ind=j-M[i][0]
        kari=res[ind]+M[i][1]
        
        ff=min(ff,kari)
    res.append(ff)
print(res[-1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    ok1 = False
    ok2 = False
    ok3 = False
    for j in range(N):
        if S[j] == pw[0] and not ok1:
            ok1 = True
            continue
        if ok1 and not ok2:
            if S[j] == pw[1]:
                ok2 = True
                continue
        if ok2:
            if S[j] == pw[2]:
                ok3 = True
                # print(pw)
                break
    if ok3:
        ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    pw = str(i).zfill(3)
    ok1 = False
    ok2 = False
    ok3 = False
    for j in range(N):
        if S[j] == pw[0] and not ok1:
            ok1 = True
            continue
        if ok1 and not ok2:
            if S[j] == pw[1]:
                ok2 = True
                continue
        if ok2:
            if S[j] == pw[2]:
                ok3 = True
                # print(pw)
                break
    if ok3:
        ans += 1

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

import itertools

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

sum = 0

for v in itertools.combinations(a, 2):
	sum += v[0]*v[1]
    
print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
# required function 
def findProductSum(A, n): 
      
    # calculating array sum (a1 + a2 ... + an) 
    array_sum = 0
    for i in range(0, n, 1): 
        array_sum = array_sum + A[i] 
  
    # calcualting square of array sum 
    # (a1 + a2 + ... + an)^2 
    array_sum_square = array_sum * array_sum 
  
    # calcualting a1^2 + a2^2 + ... + an^2 
    individual_square_sum = 0
    for i in range(0, n, 1): 
        individual_square_sum += A[i] * A[i] 
  
    # required sum is (array_sum_square - 
    # individual_square_sum) / 2 
    return (array_sum_square - 
            individual_square_sum)
mod = 10**9+7
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
  
print(modinv(2)*int(findProductSum(a, n))%mod)
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    if k in dic:
        dic[k]=0
        continue
    f=1
    for i in dic:
        if k%i==0:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

### FIXED CODE ###

M=10**6+10
c=[0]*M
n=int(input())
a=sorted(list(map(int,input().split())))
for k in a:
    if c[k]:
        c[k]=2
        continue
    for i in range(k,M,k):
        c[i]+=1
ans=0
for i in a:
    if c[i]==1:
        ans+=1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()
nums = []
now = 1
cnt = 0
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * K + 1
ans = 0
for i in range(0, len(nums), 2):
    tmp = 0

    left = i
    right = min(i + add, len(nums))
    for j in range(left, right):
        tmp += nums[j]
    ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
nums = []
now = 1
cnt = 0
for i in range(N):
    if S[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt)
        now = 1 - now
        cnt = 1
if cnt != 0:
    nums.append(cnt)
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * K + 1
ans = 0
left = 0
right = 0
tmp = 0
for i in range(0, len(nums), 2):

    next_left = i
    next_right = min(i + add, len(nums))

    while next_left > left:
        tmp -= nums[left]
        left += 1

    while next_right > right:
        tmp += nums[right]
        right += 1

    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    import numpy as np
    mod = 998244353
    dp = np.zeros((N+1, S+1), int)
    #dp[i, j]を、A[0]...A[i]までを使って、Tの空でない部分集合
    #{x_1, x_2, ..., x_k}であって、Ax_1 + A_x_2 + ... + A_x_k = jを満たすものの個数とする。
    dp[0, 0] = 1
    #iまででjが作られている時、i+1ではA[i]がどのような値であっても、部分集合としてjは作れる。
    #iまででjが作られない時、j-A[i]が作られていれば、A[i]を足せばjは作れる。
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += dp[i, j] * 2
            dp[i+1, j] %= mod
            if j >= A[i]:
                dp[i+1, j] += dp[i, j-A[i]]
                dp[i+1, j] %= mod
                    
    print(dp[N][S] % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    mod = 998244353
    dp = [[0] * ( S+1) for _ in range(N+1)]
    #dp[i, j]を、A[0]...A[i]までを使って、Tの空でない部分集合
    #{x_1, x_2, ..., x_k}であって、Ax_1 + A_x_2 + ... + A_x_k = jを満たすものの個数とする。
    dp[0][0] = 1
    #iまででjが作られている時、i+1ではA[i]がどのような値であっても、部分集合としてjは作れる。
    #iまででjが作られない時、j-A[i]が作られていれば、A[i]を足せばjは作れる。
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j] += dp[i][j] * 2 
            dp[i+1][j] %= mod
            if j >= A[i]:
                dp[i+1][j] += dp[i][j-A[i]]
                dp[i+1][j] %= mod
                    
    print(dp[N][S] % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,n+1):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))

### FIXED CODE ###

import math

P=[]
n=int(input())
N=int(math.sqrt(n))

for i in range(1,N+2):
  if n%i==0:
    p=max(len(str(i)),len(str(int(n/i))))
    P.append(p)
    
print(min(P))