Harryxun/stf_run huggingface dataset:
import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
AP=A[-p:]
if q>0:
  AN=A[:q]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp/AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  K=K-a-b
  x=0
  y=10**18
  AN=AN[::-1]
  AN=-AN
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp/AP, side='right').sum()-np.searchsorted(AP, pow(tmp, 1/2), side='right'))//2
    counter2=(np.searchsorted(AN, tmp/AN, side='right').sum()-np.searchsorted(AN, pow(tmp, 1/2), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)

### FIXED CODE ###

import numpy as np

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

p=np.sum(A>0)
q=np.sum(A<0)
Z=N-p-q
if p>0:
  AP=A[-p:]
else:
  AP=[]
if q>0:
  AN=A[:q]
else:
  AN=[]

b=(N-Z)*Z+Z*(Z-1)//2
a=p*q

if K<=a:
  x=AP[-1]*AN[0]-1
  y=AP[0]*AN[-1]
  while y-x>1:
    tmp=(y+x)//2
    counter=np.searchsorted(AN, tmp//AP, side='right').sum()
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
elif K<=a+b:
  print(0)
else:
  x=0
  y=10**18
  K=K-a-b
  if q<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  AN=AN[::-1]
  AN=-AN
  
  if p<=1:
    while y-x>1:
      tmp=(y+x)//2
      counter=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
      if counter<K:
        x=tmp
      else:
        y=tmp
    print(y)
    exit()
    
  while y-x>1:
    tmp=(y+x)//2
    counter1=(np.searchsorted(AP, tmp//AP, side='right').sum()-np.searchsorted(AP, int(pow(tmp, 1/2)), side='right'))//2
    counter2=(np.searchsorted(AN, tmp//AN, side='right').sum()-np.searchsorted(AN, int(pow(tmp, 1/2)), side='right'))//2
    counter=counter1+counter2
    if counter<K:
      x=tmp
    else:
      y=tmp
  print(y)
n = int(input())
a = [int(input()) for i in range(n)]

l = sorted(a, reverse=True)
m = a.index(a(max))
for i in range(n):
    if i == m:
        print(l[1])
    else:
        print(l[0])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

l = sorted(a, reverse=True)
m = a.index(l[0])
for i in range(n):
    if i == m:
        print(l[1])
    else:
        print(l[0])
#!/usr/bin/env python3
import sys

s = input()

swox = "".join(list(filter("x".__ne__, list(s))))

# print(s, swox)
def is_palind(a):
    for i in range(len(a)//2):
        if a[i] != a[-i-1]:
            return False
    return True

if not is_palind(swox):
    print(-1)
    sys.exit(0)
#
l = 0
r = -1
count = 0
# print(s)
while True:
    # print(l, r+len(s))
    # print(s[l],s[r])
    if l == r+len(s):
        break
    if s[l] == "x" and s[r] == "x":
        l += 1
        r -= 1
    elif s[l] == "x":
        l += 1
        count += 1
    elif s[r] == "x":
        r -= 1
        count += 1
    else:
        l += 1
        r -= 1
print(count)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

s = input()

swox = "".join(list(filter("x".__ne__, list(s))))

# print(s, swox)
def is_palind(a):
    for i in range(len(a)//2):
        if a[i] != a[-i-1]:
            return False
    return True

if not is_palind(swox):
    print(-1)
    sys.exit(0)
#
l = 0
r = -1
count = 0
# print(s)
while True:
    # print(l, r+len(s))
    # print(s[l],s[r])
    if l >= r+len(s):
        break
    if s[l] == "x" and s[r] == "x":
        l += 1
        r -= 1
    elif s[l] == "x":
        l += 1
        count += 1
    elif s[r] == "x":
        r -= 1
        count += 1
    else:
        l += 1
        r -= 1
print(count)
n, x = [int(i) for i in input().split()]

cnt=0

short = n%x
long  = x

cnt += x*(2*(n//x)-1) + (n-x)

while(1):
    c = long % short
    a = long //short
    if c==0:
        break
    else:
        cnt += short * 2 * a
        long = short
        short = c

cnt += short * 2 * a -1
print(cnt)


### FIXED CODE ###

n, x = [int(i) for i in input().split()]

cnt=0

short = min(x,n-x)
long  = max(x, n-x)
cnt += n
#cnt += x*(2*(n//x)-1) + (n-x)

while(1):
    c = long % short
    a = long //short
    if c==0:
        break
    else:
        cnt += short * 2 * a
        long = short
        short = c

cnt += short * (2 * a -1)
print(cnt)
N=int(input())
LA=[0]*N
LD=[0]*N
for i in range(N):
    A,B=input().split()
    LA[i]=int(A)
    LD[i]=int(A)+int(B)

isRunned=True
while(isRunned):
    isRunned=False
    for i in range(N-1):
        if LD[i]<LD[i+1]:    
            LD[i],LD[i+1]=LD[i+1],LD[i]
            LA[i],LA[i+1]=LA[i+1],LA[i]
            isRunned=True
        

print(sum(LA[::2])-(sum(LD[1::2])-sum(LA[1::2])))


### FIXED CODE ###

N,A,B=input().split()
N=int(N)
A=int(A)
B=int(B)
if A+B-N<0:
    print(str(min(A,B))+" 0")
else:
    print(str(min(A,B))+" "+str(A+B-N))
N, M = map(int, input().split())
#a = [0 for _ in range(N + 1)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
#a = [0 for _ in range(N + 1)]
dp = [-1 for _ in range(N + 1)]
dp[0] = 1
for _ in range(M):
    a = int(input())
    dp[a] = 0
mod = 10**9 + 7

def f(n):
    if n < 0:
        return 0
    if dp[n] == -1:
        dp[n] = (f(n - 1) + f(n - 2)) % mod
    return dp[n]
print(f(N))
a,b,n=map(int,input().split())
import math
x=b-1
if n<b-1:
    m=[math.floor(a*n/b)]
while x<=n:
    f=math.floor(a*x/b)-a*(math.floor(x/b))
    m.append(f)
    x+=b
print(max(m))

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
if n<b:
    m=math.floor(a*n/b)
else:
    e=b-1
    m=math.floor(a*e/b)
print(m)
def comb_(n,k):
    return fact(n)*fact_inv(k)*fact_inv(n-k)*pow(2,(n+1)*(mod-2),mod)%mod

f_B = defaultdict(lambda:pow(2,mod-2,mod))
f_W = defaultdict(lambda:pow(2,mod-2,mod))
g = defaultdict(lambda:pow(2,W*(mod-2),mod))

for i in range(B,B+W):
    f_B[i+1] = f_B[i]-comb_(i-1,B-1)*pow(2,mod-2,mod)
    f_B[i+1] %= mod

for i in range(W,B+W):
    f_W[i+1] = f_W[i]-comb_(i-1,W-1)*pow(2,mod-2,mod)
    f_W[i+1] %= mod

for i in range(W+1,B+W):
    g[i+1] = g[i] + comb_(i-1,W-1)
    g[i+1] %= mod

for i in range(1,B+W+1):
    if i < W+1:
        print(f_B[i])
    else:
        print((f_B[i]+f_W[i]+g[i]-pow(2,mod-2,mod))%mod)


### FIXED CODE ###

from collections import defaultdict
B,W = map(int,input().split())
mod = 10**9+7

fact = [0]*(10**6+1)
fact[0] = 1
for i in range(10**6):
    fact[i+1] = fact[i]*(i+1)%mod

def comb_(n,k):
    return fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod)*pow(2,(n+1)*(mod-2),mod)%mod

f_B = defaultdict(lambda:pow(2,mod-2,mod))
f_W = defaultdict(lambda:pow(2,mod-2,mod))
g = defaultdict(lambda:pow(2,W*(mod-2),mod))

for i in range(B,B+W):
    f_B[i+1] = f_B[i]-comb_(i-1,B-1)*pow(2,mod-2,mod)
    f_B[i+1] %= mod

for i in range(W,B+W):
    f_W[i+1] = f_W[i]-comb_(i-1,W-1)*pow(2,mod-2,mod)
    f_W[i+1] %= mod

for i in range(W+1,B+W):
    g[i+1] = g[i] + comb_(i-1,W-1)
    g[i+1] %= mod

for i in range(1,B+W+1):
    if i < W+1:
        print(f_B[i])
    else:
        print((f_B[i]+f_W[i]+g[i]-pow(2,mod-2,mod))%mod)
P, Q, R = map(int, input()split())
print(min(P+Q, Q+R, R+A))

### FIXED CODE ###

P, Q, R = map(int, input().split())
print(min(P+Q, Q+R, R+P))
import re
 
a = []
for i in range(5):
    a.append(input().split())
n = int(a[0][0])
q = int(a[0][1])
str = a[1][0]
b = a[2:]
for i in b:
  l = int(i[0])
  r = int(i[1])
  sub_str = str[(l-1):r]
  print(len(re.findall('AC', sub_str)))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
n = list(map(int,input().split()))
for i in range(n):
  if n[i] == 0:
    print(i)
    break

### FIXED CODE ###

n = [int(x) for x in input().split()]
for i in range(len(n)):
  if n[i] == 0:
    print(i + 1)
    break
S = input()
l = len(S)
T = list(S)


tmp = 0

while tmp != len(T)-1:
    if T[tmp] != T[tmp+1]:
     
        T.pop(tmp)
        T.pop(tmp)
        tmp -= 1
    else:

        tmp += 1





k = len(T)

ans = l - k

print(ans)



### FIXED CODE ###

S = input()
l = len(S)
T = list(S)


tmp = 0

while tmp < len(T)-1:
    if T[tmp] != T[tmp+1]: 
        T.pop(tmp)
        T.pop(tmp)
        if tmp == 0:
            tmp = 0
        else:
            tmp -= 1
    else:
        tmp += 1


k = len(T)

ans = l - k

print(ans)
from math import log2, floor

h = int(input())
tmp = floor(log2(h)) + 1
print(2 ** tmp - 1)


### FIXED CODE ###

from math import log2, floor

h = int(input())
tmp = floor(log2(h)) + 1
print(2 ** tmp - 1)
def main():
    h,w = map(int,input().split())
    sy,sx = map(int,input().split())
    gy,gx = map(int,input().split())
    S = []
    for _ in range(h):
        S.append(input())
    
    G = [[-1]*w for _ in range(h)]
    G_b = [[False]*w for _ in range(h)]
    v = [(1,0),(0,1),(-1,0),(0,-1)]
    ct = 0

    dq1 = deque([])
    dq1.append((sx-1,sy-1))
    G[sy-1][sx-1] = 0
    G_b[sy-1][sx-1] = True


    while dq1:

        g = set([])
        while dq1:
            x,y = dq1.popleft()
            g.add((x,y))
            for vx,vy in v:
                nx = x+vx
                ny = y+vy
                if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                    G_b[ny][nx] = True
                    G[ny][nx] = ct
                    dq1.append((nx,ny))

        
        while g:
            x,y = g.pop()
            for i in range(-2,3):
                for j in range(-2,3):
                    if i!=0 or j!=0:
                        nx = x+i
                        ny = y+j
                        if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                            dq1.append((nx,ny))
                            G_b[ny][nx] = True
                            G[ny][nx] = ct+1


        ct+=1
    
    print(G[gy-1][gx-1])
main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    sy,sx = map(int,input().split())
    gy,gx = map(int,input().split())
    S = []
    for _ in range(h):
        S.append(input())
    
    G = [[-1]*w for _ in range(h)]
    G_b = [[False]*w for _ in range(h)]
    v = [(1,0),(0,1),(-1,0),(0,-1)]
    ct = 0

    dq1 = deque([])
    dq1.append((sx-1,sy-1))
    G[sy-1][sx-1] = 0
    G_b[sy-1][sx-1] = True


    while dq1:

        g = set([])
        while dq1:
            x,y = dq1.popleft()
            g.add((x,y))
            for vx,vy in v:
                nx = x+vx
                ny = y+vy
                if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                    G_b[ny][nx] = True
                    G[ny][nx] = ct
                    dq1.append((nx,ny))

        
        while g:
            x,y = g.pop()
            for i in range(-2,3):
                for j in range(-2,3):
                    if i!=0 or j!=0:
                        nx = x+i
                        ny = y+j
                        if nx>=0 and nx<w and ny>=0 and ny<h and (not G_b[ny][nx]) and S[ny][nx]==".":
                            dq1.append((nx,ny))
                            G_b[ny][nx] = True
                            G[ny][nx] = ct+1


        ct+=1
    
    print(G[gy-1][gx-1])

main()
import fractions
a,b = map(int, input().split())
g = fractions.gcd(a,b)
l = [0]*(g-1)

for i in range(2, g+1):
  if g%i == 0 and min(a,b)%i == 0:
    for j in range(2, i):
      if i%j == 0:
        break
    else:
      l[i] = 1

print(l.count(1)+1)

### FIXED CODE ###

import fractions
import math
a,b = map(int, input().split())
g = fractions.gcd(a,b)
ans = 1

for i in range(2, int(math.sqrt(g))+1):
  if g%i == 0:
    ans += 1
    while True:
      g //= i
      if g%i != 0:
        break
if (g != 1):
  ans += 1
print(ans)
N, M = map(int, input().split())

empty = [True]*N

for m in range(M, 0, -1):
  i = 0
  while not(empty[i] and empty[i + m]):
    i += 1
  empty[i] = False
  empty[i+m] = False
  print(i+1, i+m+1)

### FIXED CODE ###

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

halfPos = -(-N//2)

qPos = halfPos // 2

q3Pos = qPos + halfPos

for m in range(1, M+1):
  if m % 2:
    print(qPos-m//2, qPos+m//2+1)
  else:
    print(q3Pos-m//2, q3Pos+m//2)
import numpy as np

def search(now,r,dist,ans):
    if len(r)==0:
        return ans
    min_=float('inf')
    for i,x in enumerate(r):
        if i < len(r)-1:
            min_=min(min_,search(x,r[:i]+r[i+1:],dist,ans+dist[now][x]))
        else:
            min_=min(min_, search(x,r[:i],dist,ans+dist[now][x]))
    return min_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=np.array(dist)

ans=float('inf')
for i in range(N):
    for j in range(N):
        dist[i][j]=min(dist[i]+dist[j])

ans=float('inf')
for i,x in enumerate(r):
    if i < len(r)-1:
        ans=min(ans, search(x,r[:i]+r[i+1:],dist,0))
    else:
        ans=min(ans, search(x,r[:i],dist,0))
if ans==float('inf'):
    print(0)
else:
    print(int(ans)

### FIXED CODE ###

from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall as ws

def search(r,dist,ans):
    sum_=0
    for i in range(1,len(r)):
        sum_+=dist[r[i-1]][r[i]]
    return sum_

N,M,R=list(map(int,input().split()))
r=list(map(int,input().split()))
r=[x-1 for x in r]
dist=[[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A,B,C=list(map(int,input().split()))
    dist[A-1][B-1]=C
    dist[B-1][A-1]=C
for i in range(N):
    dist[i][i]=0
dist=ws(dist)

ans=float('inf')

ans=float('inf')
r=permutations(r)
for x in r:
    ans=min(ans,search(x,dist,0))
print(int(ans))
s = input()
a = int(s)
mods = [a%2019]
for i in range(len(s)):
  a = int((a-int(s[-(i+1)]))/10)
  mods.append(a%2019)
mod_N ={}
for i in mods:
  if not i in mod_N:
    mod_N[i] = 1
  else:
    mod_N[i] += 1
ans = 0
for i in mod_N:
  ans += int(mod_N[i]*(mod_N[i]-1)/2)
print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
S,T=map(str,input().split())
S_list=list(S)
T_list=list(T)
count=0
for i in range(len(S)):
    if S[i]==T[i]:
        count+=1
if count==len(S_list):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S=str(input())
T=str(input())
S_list=list(S)
T_list=list(T)
count=0
for i in range(len(S)):
    if S[i]==T[i]:
        count+=1
if count==len(S_list):
    print("Yes")
else:
    print("No")
import sys
read=sys.stdin.read

def main():
  n,h,*ab=map(int,read().split())
  tops=max(ab[0::2])
  tlst=[b for b in ab[1::2] if b>tops]
  tlst.sort(reverse=True)
  for i,t in enumerate(tlst):
    h-=t
    if h<=0:
      h=0
      return
  print(h//tops+(h%tops>0)+i+1)

if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
read=sys.stdin.read

def main():
  n,h,*ab=map(int,read().split())
  tops=max(ab[0::2])
  tlst=[b for b in ab[1::2] if b>tops]
  tlst.sort(reverse=True)
  i=-1
  t=0
  for i,t in enumerate(tlst):
    h-=t
    if h<=0:
      h=0
      break
  print(h//tops+(h%tops>0)+i+1)

if __name__=='__main__':
  main()
s=input()
if(s[-1:]=='s'):
  print(s[-1].replace("s","es"))
else:
  s1=s+"s"
print(s1)

### FIXED CODE ###

s=input()
if(s[-1:]=='s'):
  s1=s+"es"
  print(s1)
else:
  s2=s+"s"
  print(s2)
N,M=map(int,input().split())
A=list(input() for _ in range(N))
B=list(input() for _ in range(M))
ans="No"
for y in range(N-M+1):
    for x in range(N-M+1):
        if A[y][x]==B[0][0]:
            cond=True
            for i in range(N-M):
                if A[y+i][x:x+M]!=B[i]:
                    cond=False
                    break
            if cond:
                ans="Yes"
                break
    if ans=="Yes":
        break

print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(input() for _ in range(N))
B=list(input() for _ in range(M))
ans="No"
for y in range(N-M+1):
    for x in range(N-M+1):
        if A[y][x:x+M]==B[0]:
            cond=True
            for i in range(M):
                if A[y+i][x:x+M]!=B[i]:
                    cond=False
                    break
            if cond:
                ans="Yes"
                break
    if ans=="Yes":
        break
print(ans)
print('YNeos'[1-'2'in input()::2])

### FIXED CODE ###

A,B=map(int,input().split())
if A*B % 2:
    print('Yes')
else:
    print('No')
s = set(list("abcdefghijklmnopqrstuvwxyz"))-set(list(input()))
if len(s)==0:
  print("None")
else:
  print(s[0])

### FIXED CODE ###

s = set(list("abcdefghijklmnopqrstuvwxyz"))-set(list(input()))
if len(s)==0:
  print("None")
else:
  print(min(s))
s=input()
l='abcdefghijklmnopqrstuvwxyz'
s=''.join(list(set(s)))
s=sorted(s)
f=0
for i in range(26):
    if(s[i]!=l[i]):
        print(l[i])
        f=1
        break
if(f==0):
    print('None')


### FIXED CODE ###

s=input()
l='abcdefghijklmnopqrstuvwxyz'
for i in range(26):
    if(s.count(l[i])==0):
        print(l[i])
        exit()
print('None')
def Dictionary(b):
    a=list(map(int,input().split()))
    if(a[0] == "insert"):
        b.append(a[1])
    elif(a[0] == "find"):
        if(a[1] in b):
            print("yes")
        else:
            print("no")

if __name__ == "__main__":
    n=int(input())
    b=[]
    for i in range(n):
        Dictionary(b)
    
            


### FIXED CODE ###

import sys
d={}
input()
for i in sys.stdin:
    if i[0] == "i":
        d[i[7:]]=0
    else:
        if i[5:] in d:
            print("yes")
        else:
            print("no")
k, yen = input().split()
print('Yes') if k*500>=yen else print('No)

### FIXED CODE ###

[k, yen] = [int(x) for x in input().split()]
print('Yes') if k*500>=yen else print('No')
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    for i in [1,2] + list(range(3,num+1)):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
import math
r = int(input())
print('%.6f' % (r * r * math.pi), '%.6f' % (2 * math.pi * r))

### FIXED CODE ###

import math
r = float(input())
print('%.5f' % (r * r * math.pi), '%.5f' % (2 * math.pi * r))
# -*- coding: utf-8 -*-
import copy

H,W,K=map(int, raw_input().split())
S=[ list(raw_input()) for _ in range(H)]

L=[ [] for _ in range(H) ]
ng=[]

cnt=0
ichigo=False
for h in range(H):
    cnt+=1
    ichigo=False
    for w in range(W):
        if S[h][w]=="#":
            if ichigo:
                cnt+=1      ##該当行でイチゴの出現が2回目以降の時は、カウントを増やす
            else:
                ichigo=True #該当行でイチゴの出現が1回目の時はTrueを入れる
        L[h].append(cnt)
    else:
        if ichigo is False:
            ng.append(h) #イチゴが１つも入ってない行番号



def func(n,str):   #行番号 方向 u:up d:down
    #print "func(",n,",",str,")"
    if n in ng:
        if 0<=n-1: func(n-1,"u")
        if n+1<=H-1: func(n+1,"d")
    else:      #NG行でない場合
        if str=="u":
            if n+1<=H-1:
                L[n+1]=copy.deepcopy(L[n])
        elif str=="d":
            if 0<=n-1:
                L[n-1]=copy.deepcopy(L[n])

#1行にイチゴが1つもない行に対して、前or後の行をコピーする処理
for x in ng:
    func(x,"u")
    func(x,"d")


#1,2,3...Kの順で再度ピースの番号を振り直す
D={}    #前のピース番号：後のピース番号のマッピング辞書配列

cnt=1
for h in range(H):
    for w,x in enumerate(L[h]):
        if x not in D:  #辞書内になかった場合は、辞書に登録してカウンターの数字を+1する
            D[x]=cnt
            L[h][w]=cnt
            cnt+=1
        else:
            L[h][w]=D[x]  #辞書内にあった場合は、その値を使用


for h in range(H):
    for x in L[h]:
        print x,
    print

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque,defaultdict
sys.setrecursionlimit(10**5)

H,W,K=map(int, sys.stdin.readline().split())
ichigo=[]
cnt=0
h_visit=[0 for h in range(H)]  #縦軸にイチゴがない箇所は0、ある箇所は1

L=[ [] for h in range(H) ]
for h in range(H):
    s=sys.stdin.readline().strip()
    for w,x in enumerate(s):
        if x==".":
            L[h].append(0)
        elif x=="#":
            cnt+=1
            L[h].append(cnt)
            ichigo.append((h,w))
            h_visit[h]=1


D=(1,-1)

def yoko_dfs(h,w):  #縦座標、横座標
    for dw in D:
        if 0<=w+dw<=W-1 and L[h][w+dw]==0:
            L[h][w+dw]=L[h][w]
            yoko_dfs(h,w+dw)
    return

for h,w in ichigo:
    yoko_dfs(h,w)


def tate_dfs(h):  #縦座標
    for dh in D:
        if 0<=h+dh<=H-1:
            if h_visit[h+dh]==1: continue
            h_visit[h+dh]=1 #訪問済みにする
            L[h+dh]=L[h]
            tate_dfs(h+dh)

for h,w in ichigo:
    tate_dfs(h)

for l in L:
    for x in l:
        print x,
    print
n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

cum_ones = []
for i, num in enumerate(ones):
    if i == 0:
        cum_ones.append(num)
        continue
    cum_ones.append(num + cum_ones[-1])
cum_zeros = []
for i, num in enumerate(zeros):
    if i == 0:
        cum_zeros.append(num)
        continue
    cum_zeros.append(num + cum_zeros[-1])

max_score = 0
for i in range(n_zeros - k + 1):
    score = 0
    score += (cum_ones[i+k] - cum_ones[i-1]) if i > 0 else cum_ones[i+k]
    if k > 0:
        score += (cum_zeros[i+k-1] - cum_zeros[i-1]) if i > 0 else cum_zeros[i+k]
    if max_score < score:
        max_score = score

print(max_score)


### FIXED CODE ###

n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

cum_ones = []
for i, num in enumerate(ones):
    if i == 0:
        cum_ones.append(num)
        continue
    cum_ones.append(num + cum_ones[-1])
cum_zeros = []
for i, num in enumerate(zeros):
    if i == 0:
        cum_zeros.append(num)
        continue
    cum_zeros.append(num + cum_zeros[-1])

max_score = 0
for i in range(n_zeros - k + 1):
    score = 0
    score += (cum_ones[i+k] - cum_ones[i-1]) if i > 0 else cum_ones[i+k]
    if k > 0:
        score += (cum_zeros[i+k-1] - cum_zeros[i-1]) if i > 0 else cum_zeros[i+k-1]
    if max_score < score:
        max_score = score

print(max_score)