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

import numpy as np

def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))

### FIXED CODE ###

import numba
from numba import jit
import numpy as np
 
#(i,j)→(i+1,j)のように動くときはアイテムを入手できる回数がリセットされる
#dp[列][今、何個アイテムを取ったか]でdpテーブルを作る
@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in list(input().split())])
    for i in range(p):
        dp[i|c] = min(dp[i|c], dp[i] + a)
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(i-1) for i in map(int, input().split())])
    for i in range(p):
        if dp[i|c] > dp[i] + a: 
            dp[i|c] = dp[i] + a
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()

cnt = 0
for i in range(0,N-2):
  for j in range(i+1,N-1):
    t = L[i]+L[j]
    idx = bisect_left(L,t,lo=j+1)
    cnt += max(0,idx-j-1)
print(cnt)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()

from bisect import bisect_left 
cnt = 0
for i in range(0,N):
  for j in range(i+1,N):
    t = L[i]+L[j]
    idx = bisect_left(L,t)
    cnt += max(0,idx-j-1)
print(cnt)
### BUGGY CODE ###

k = int(input())
k = [int(x)+1 for x in range(k)]
#print(k)
from fractions import gcd
from itertools import product,combinations
from functools import reduce
num = 0

for v in product(k,repeat =3):
    v = (list(v))
    
    a = reduce(gcd,v)
    num +=a
    #print(v,num)
print(num)

### FIXED CODE ###

k = int(input())
import math
num = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = math.gcd(i,j)
        for l in range(1,k+1):
            b = math.gcd(a,l)
            num += b
print(num)
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n + 1):
  cnt = 0
  for s in range(int(math.sqrt(n)) + 1 + 1):
    for x in range(1, s + 1):
      for y in range(1, s - x + 1):
        z = s - x - y
        if 1 <= z:
          if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == i:
            cnt += 1
  print(cnt)


### FIXED CODE ###

import math

n = int(input())

cnts = [0] * (n + 1)
sn = int(math.sqrt(n)) + 1
for x in range(1, sn + 1):
  for y in range(1, sn + 1):
    for z in range(1, sn + 1):
      g = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
      if 1 <= g <= n:
        cnts[g] += 1

for i in range(1, n + 1):
  print(cnts[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*200010
    now = 0
    l[0] = 0
    ans = -100

    for i in range(n):
        a[i] -= 1

    for i in range(n*2):
        k -= 1
        now = a[now] #転送された場所
        l[now] += 1
        if l[now] == 2: #3ループ目の頭
            loop = l.count(1) + 1
            k %= loop
        if k == 0:
            ans = now + 1
            break

    print(max(ans, -1))

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()
### BUGGY CODE ###

X=input()
a=list()
for i in range(len(X)):
    a.append(int(X[i:len(X)])%2019)
S=a.count(0)
for j in range(1,2018):
    S+=int(a.count(j)*(a.count(j)-1)/2)
print(S)    


### FIXED CODE ###

A=[0]*2019
s=input()
a=0
b=1
for i in range(len(s)):
    b=b%2019
    a=(a+int(s[len(s)-1-i])*b)%2019
    b=b*10
    A[a]+=1
x=A[0]
for j in range(2019):
    x+=int(A[j]*(A[j]-1)/2)
print(x)
### BUGGY CODE ###

def make_divisors(n):
  lower_divisors , upper_divisors = [], []
  i = 1
  while i*i <= n:
    if n % i == 0:
      lower_divisors.append(i)
      if i != n // i:
        upper_divisors.append(n//i)
    i += 1
  return lower_divisors + upper_divisors[:0:-1]

N = int(input())
As = list(map(int, input().split()))
st = set(As)
Fs = [0]*N
 
As.sort()
if N == 1:
  print(1)
  exit()
else:
  rlt = 1
  
for i in range(1,N):
  if As[i] == As[i-1]:
    Fs[i] = 1
    if Fs[i-1] == 0:
      rlt -= 1
    continue
  ls =  make_divisors(As[i])
  for l in ls:
    flag = 0
    if l in st:
      Fs[i] = 1
      flag = 1
      break
  if flag == 0:
    rlt += 1
    
print(rlt)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
 
As.sort()
 
st = set(As)
m = As[-1]
rlt = 0
Fs = [1]*(m+1)
 
for i in range(N):
  if i > 0 and As[i] == As[i-1]:
    Fs[As[i]] = 0
    continue
  j = 2
  while As[i]*j <= m:
    Fs[As[i]*j] = 0
    j += 1

for a in As:
  rlt += Fs[a]
    
print(rlt)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [0] * n
p = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
while q:
    next = q.popleft()
    v[next -1] = 1
    for i in t[next]:
        if v[i - 1] == 0 and i not in q:
            q.append(i)
            p[i - 1] = next
print('Yes')
print(*p[1:], sep='\n')

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(len(s)):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)

# print(r)
# print(g)
# print(b)

ans = 0
for R in r:
    for G in g:
        for B in b:
            lst = [R,G,B]
            lst.sort()
            if lst[1]-lst[0]!=lst[2]-lst[1]:
                ans += 1
print(ans)


### FIXED CODE ###

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

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = j + (j-i)
        if k<n and set([s[i],s[j],s[k]])==set(["R","G","B"]):
            ans -= 1
print(ans)
### BUGGY CODE ###

ls = []
for i in range(int(input())):
    command, text = input().split()
    if command == "insert":
        ls.append(text)

    else:
        if ls.count(text) >= 1:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

dic = {}
line = []
for i in range(int(input())):
    line.append(input().split())
for i in line:
    if i[0][0] == "i":
        dic[i[1]] = None
    else:
        print("yes" if i[1] in dic else "no")
### BUGGY CODE ###

N,M = map(int,input().split())
gcd = M // N
gcd_tmp = 0
while gcd > 0:
 tmp = M - gcd
 if tmp % gcd == 0:
  gcd_tmp = gcd
  break
 gcd = gcd - 1
print(gcd_tmp)

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

s = input()
q = int(input())
li=[list(map(str,input().split())) for _ in range(q)]

que = []
frag = True

for i in range(q):
    que = li[i]
    if que[0] == "1":
        if frag:
            frag = False
        else:
            frag = True
    else:
        f = que[1]
        c = que[2]
        if frag:
            if f == "1":
                s = c + s
            else:
                s = s + c
        else:
            if f == "1":
                s = s + c
            else:
                s = c + s

if frag:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
li=[list(map(str,input().split())) for _ in range(q)]

moji = "0"
frag = True

for i in range(q):
    que = li[i]
    if que[0] == "1":
        if frag:
            frag = False
        else:
            frag = True
    else:
        f = que[1]
        c = que[2]
        if frag:
            if f == "1":
                moji = c+moji
            else:
                moji = moji+c
        else:
            if f == "1":
                moji = moji+c
            else:
                moji = c+moji


if frag:
    print(moji.replace("0",s))
else:
    moji = moji[::-1]
    print(moji.replace("0",s[::-1]))
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
        if j==14:
            ddprint("dp {} z {} acc {}".format(dp[z-1][j-1], z, acc[z]))
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R
        if i==18 and j==14:
            ddprint("{}  {}  {}".format(dp[i][j-1], acc[i], t[j]==s[0]))
        ddprint("i {} j {} dpij {}".format(i,j,dp[i][j]))

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
R = 10**9 + 7
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = inl()
t = inl()
dp = [ [0] * (m+1) for i in range(n) ]
dp[0][0] = 1 if s[0]==t[0] else 0
for i in range(1,n):
    dp[i][0] = dp[i-1][0] + (1 if s[i]==t[0] else 0)
for j in range(1,m):
    dp[0][j] = dp[0][j-1] + (1 if s[0]==t[j] else 0)

sh = defaultdict(list)
for i in range(1,n):
    sh[s[i]].append(i)

for j in range(1,m):
    x = 0
    acc = [0] * (n+1)
    for z in sh[t[j]]:  # s[z]==t[j]
        x = (x+dp[z-1][j-1]+1)%R  # z>0
        acc[z] = x
    for i in range(1,n):
        acc[i] = (acc[i-1] if acc[i]==0 else acc[i])

    for i in range(1,n):
        x = dp[i][j-1]
        #for z in sh[t[j]]:  # s[z]==t[j]
        #  if z<=i:
        #    x = (x+dp[z-1][j-1]+1)%R  # z>0
        x += acc[i]
        if t[j]==s[0]:
            x += 1
        dp[i][j] = x%R

if DBG:
    for i in range(n):
        print(dp[i])
print((dp[n-1][m-1]+1)%R)
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for _ in range(M):
  B,C = map(int,input().split())
  index = min(bisect.bisect_left(A,C), B)
  if index==0:
    continue
  for i in range(index):
    A[i] = C
  A.sort()
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
D = []
for _ in range(M):
  D.append(list(map(int,input().split())))
D.sort(key=lambda x:x[1], reverse=True)
cnt = 0
ans = []
for d in D:
  b,c = d[0],d[1]
  ans += [c for _ in range(b)]
  cnt += b
  if cnt>=N:
    break
ans = ans[:min(cnt,N)] + A
ans.sort(reverse=True)
print(sum(ans[:N]))
### BUGGY CODE ###

from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])

### FIXED CODE ###

from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

"""
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])
"""

if n == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    #print(mov_num)

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
if now_num == A[n]:
    print(now_total)
else:
    print(-1)
### BUGGY CODE ###

N, K = map(int, input().split())
lst = [int(x) for x in input().split()]
n = 0
ret_lst = []
for i in range(len(lst) - K + 1):
    if n < sum(lst[i : i + K]):
        n = sum(lst[i : i + K])
        ret_lst = lst[i : i + K]

ret = 0
for x in ret_lst:
    ret += sum(range(1, x + 1)) / x
print(ret)


### FIXED CODE ###

N, K = map(int, input().split())
lst = [int(x) for x in input().split()]
tmp = sum(lst[:K])
ret = tmp
for i in range(N - K):
    tmp -= lst[i]
    tmp += lst[i + K]
    ret = max(ret, tmp)
print((ret + K) / 2)
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
#h = [[i, h[i-1]] for i in range(1, n+1)]
path = [list(map(int, input().split())) for i in range(m)]
#conn = {key: [] for key in range(1, n+1)}
tower = list(range(1, n+1))


for p in path:
    # h0 > h1
    if h[p[0]-1] == h[p[1]-1]:
        if p[0] in tower:
            tower.remove(p[0])
        if p[1] in tower:
            tower.remove(p[1])
    elif h[p[0]-1] > h[p[1]-1]:
        if p[1] in tower:
            tower.remove(p[1])
    else:
        if p[0] in tower:
            tower.remove(p[0])

print(len(tower), end="")


### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
# h = [[i, h[i-1]] for i in range(1, n+1)]
# path = [list(map(int, input().split())) for i in range(m)]
# conn = {key: [] for key in range(1, n+1)}
tower = list(range(1, n+1))
ma = [0]*n

for i in range(m):
    p = list(map(int, input().split()))
    ma[p[0]-1] = max(ma[p[0]-1], h[p[1]-1])
    ma[p[1]-1] = max(ma[p[1]-1], h[p[0]-1])
    """
    # h0 > h1
    if h[p[0]-1] == h[p[1]-1]:
        if p[0] in tower:
            tower.remove(p[0])
        if p[1] in tower:
            tower.remove(p[1])
    elif h[p[0]-1] > h[p[1]-1]:
        if p[1] in tower:
            tower.remove(p[1])
    else:
        if p[0] in tower:
            tower.remove(p[0])
    """
cnt = 0
for i in range(n):
    cnt += (h[i] > ma[i])
print(cnt, end="")
### BUGGY CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp=[[[0]*3 for i in range(s+1)] for j in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      x=dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1]
      dp[i+1][j][1]=x%mod
      dp[i+1][j][2]=(x+dp[i][j][2])%mod
    else:
      dp[i+1][j][0]=dp[i][j][0]%mod
      dp[i+1][j][1]=(dp[i][j][0]+dp[i][j][1])%mod
      dp[i+1][j][2]=(dp[i][j][0]+dp[i][j][1]+dp[i][j][2])%mod
print(dp[n][s][2])

### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0 for i in range(s+1)] for j in range(n+1)]
dp1=[[0 for i in range(s+1)] for j in range(n+1)]
dp2=[[0 for i in range(s+1)] for j in range(n+1)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])
### BUGGY CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
    else:
        h = mid
check(h)
check(l)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
        ls = ms
    else:
        h = mid
check(h)
check(l)
### BUGGY CODE ###

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=[1]

for i in range(n):
    count=0
    v=0
    for j in range(L[i],n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L.append(j)
                v+=1
                
            
        if count==k+1:
            
            if i==0:
                ans=j-1
                break
                
            else:
                ans=max(ans,j-L[i])
                break
            
        if s[j]=='E':
            ans=max(ans,j-L[i])
            print(ans)
            exit()
        

### FIXED CODE ###

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

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
count=0
L2=[1]
for i in range(n):
    if i>=1:
        count-=1
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1):
            if s[j-1]==str(0):
                L2.append(j)
                
            
        if count==k+1:
            
            ans=max(ans,j-L2[i])
            #次はｊ+１から始める
            L=j+1
            break
            
        if s[j]=='E':
            ans=max(ans,j-L2[i])
            print(ans)
            exit()
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline

N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()

side = [[]for i in range(N)]
for i in range(N-1):
    a,x = cityx[i]
    b,y = cityx[i+1]
    side[x].append([b-a,y])
    side[y].append([b-a,x])
for i in range(N-1):
    a,x = cityy[i]
    b,y = cityy[i+1]
    side[x].append([b-a,y])
    side[y].append([b-a,x])

f = [1] + [0] * (N-1)
queue = side[0][:]
ans = 0
heapq.heapify(queue)
while queue:
    cost, q = heapq.heappop(queue)
    if f[q] == 0:
        ans += cost
        f[q] = 1
        for a,b in side[q]:
            heapq.heappush(queue,[a,b])

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

print(ans)