Harryxun/stf_run huggingface dataset:
n, t = map(int, input().split())

class Item:

    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.density = value / weight

    def __str__(self):
        return f'weight = {self.weight}, value = {self.value}'


class Knapsack:

    def __init__(self, weight_limit):
        self.weight_limit = weight_limit
        self.weight = 0
        self.value = 0
        self.items = []

    def add(self, item):
        if self.weight + item.weight <= self.weight_limit:
            self.weight += item.weight
            self.value += item.value
            self.items.append(item)

    def show(self):
        return self.value


def buildItems():
    lst = []
    weights = []
    values = []
    for i in range(n):
        lsti = list(map(int, input().split()))
        lst.append(lsti)
    lst.sort(key= lambda x: x[1])
    saidai = lst.pop()[1]
    for i in range(n-1):
        weights.append(lst[i][0])
        values.append(lst[i][0])
    return [Item(*params) for params in zip(values, weights)], saidai


def testGreedys(weight_limit=t-1):
    def packing(greedy):
        knapsack = Knapsack(weight_limit)
        for item in sorted(items, key=greedy, reverse=True):
            knapsack.add(item)
        return knapsack.show()

    items, saidai = buildItems()
    ans1 = packing(lambda item: item.value)    # 高価値優先
    ans2 = packing(lambda item: -item.weight)  # 軽量優先
    ans3 = packing(lambda item: item.density)  # 高密度優先
    print(max(ans1, ans2, ans3)+saidai)

if __name__ == '__main__':
    testGreedys()

### FIXED CODE ###

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

lst.sort(key=lambda x: x[0])
a, b = [], []
for i in range(n):
    lsti = lst[i]
    a.append(lsti[0])
    b.append(lsti[1])

# DPテーブルの作成
dp = [[-1 for i in range(t)] for j in range(n+1)]
for i in range(t):
    dp[0][i] = 0

# DPテーブルの更新
for i in range(n):
    for j in range(t):
        if j >= a[i]:
            dp[i+1][j] = max(dp[i][j-a[i]]+b[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

# 答え(最大となる合計価値)
kouho = []
for i in range(n):
    kouho.append(dp[i][t-1]+b[i])
kouho.append(dp[n][t-1])
print(max(kouho))
# -*- coding: utf-8 -*-
from queue import Queue

N = int(input())
a = sorted([int(n) for n in input().split()], reverse=True)

alone = a.count(max(a) - 1)

if alone:
    a = [a_ - alone for a_ in a][alone:]
    if len(a) == 2 and a[0] == 1:
        print("Yes")
    elif 2*a[0] <= len(a) and a[0] <= len(a)//a[0]:
        print("Yes")
    else:
        print("No")

else:
    if a[0] == N - 1:
        print("Yes")
    elif 2*a[0] <= len(a) and a[0] <= len(a)//a[0]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
def inpl(): return map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

C = Counter(A)

if len(C) >= 3:
    print("No")
elif len(C) == 1:
    for k, v in C.items():
        if k == N-1 or N >= 2*k:
            print("Yes")
        else:
            print("No")
else:
    k = sorted(C.keys())[0]
    v = C[k]
    X = N - v
    if (k+1-v) * 2 <= C[k+1] and v <= k:
        print("Yes")
    else:
        print("No")
a, b = int(input().split())
print(a*b
)


### FIXED CODE ###

a, b = (int(x) for x in input().split())
print(a*b, 2*a + 2*b)
import fractions
a,b=input().split()
a=int(a)
b=int(b)
lcm=a*b/fractions.gcd(a,b)
print(int(lcm))

### FIXED CODE ###

a=input()
b=input()
print(6-int(a)-int(b))
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N,M = map(int,input().split())
if M == 0:
  print(FibRe(N+2))
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)


### FIXED CODE ###

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

N,M = map(int,input().split())
if M == 0:
  P = Fib(N+2)
  print(P%1000000007)
else:
  S = []
  for _ in range(M):
    S.append(int(input()))
  S.append(-1)
  S.append(N+1)
  S.sort()  
  P = 1

  for i in range(M+1):
    P *= Fib(S[i+1]-S[i]) 

  print(P%1000000007)
# A - Getting Difference
from fractions import gcd

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n-1):
    if i==0:
        t=gcd(a[i],a[i+1])
        continue
    t=gcd(t,a[i+1])
if k%t!=0:
    print('IMPOSSIBLE')
    exit()

a_max=max(a)
b=a_max-k

if b<0:
    print('IMPOSSIBLE')
    exit()
elif b==0:
    print('POSSIBLE')
    exit()

even_count=0
odd_count=0

for aa in a:
    if aa%2==0:
        even_count+=1
    else:
        odd_count+=1
a.sort()
sa=[]
for i in range(n-1):
    if abs(a[i+1]-a[i])!=0:
        sa.append(abs(a[i+1]-a[i]))
sa.sort()


is_even=False
is_odd=False
for ssaa in sa:
    if ssaa%2==0:
        if ssaa<=b:
            is_even=True
    else:
        if ssaa<=b:
            is_odd=True

if is_even==True and is_odd==True:
    print('POSSIBLE')
elif is_even==True and is_odd==False:
    if odd_count>0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
elif is_even==False and is_odd==True:
    if even_count>0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
if k>max(a):
  print("IMPOSSIBLE")
  exit(0)

from fractions import gcd
gcd_v=a[0]
for i in range(1,n):
  gcd_v=gcd(a[i],gcd_v)
for aa in a:
  if (aa-k)%gcd_v==0:
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    elif N == 1:
        print(1)
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if A_list and N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i-1] > 1000000007:
            Dp_list[i-1] -= 1000000007
            Dp_list[i] -= 1000000007
	print(Dp_list[N]%1000000007)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
a,b,c,k = map(int,input().split())
 
if k <= a:
  print(a)
elif a < k and k <= a+b:
  print(a)
elif a+b < k and k <= a+b+c
  print(a-k+a+b)

### FIXED CODE ###

a,b,c,k = map(int,input().split())
 
if k <= a:
  print(k)
elif a < k and k <= a+b:
  print(a)
else:
  print(a-k+a+b)
A, B, C, D, E, F = map(int, input().split())
density = 0
for i in range(F//(100*A) +1):
    for j in range((F-100*A*i)//(100*B)+1):
        water = 100*A*i + 100*B*j
        if water == 0:
            continue
        for k in range((F-water)//C+1):
            for l in range((F-water-C*k)//D+1):
                sugar = C*k + D*l
                if density < sugar/(sugar + water) and sugar <= (E/100)*water:
                    density = sugar/(sugar + water)
                    ans = [sugar+water, sugar]
print(ans)

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())
density = 0
for i in range(F//(100*A) +1):
    for j in range((F-100*A*i)//(100*B)+1):
        water = 100*A*i + 100*B*j
        if water == 0:
            continue
        for k in range((F-water)//C+1):
            for l in range((F-water-C*k)//D+1):
                sugar = C*k + D*l
                if density <= sugar/(sugar + water) and sugar <= (E/100)*water:
                    density = sugar/(sugar + water)
                    ans = [sugar+water, sugar]
print(ans[0], ans[1])
n = int(input())

if n%2 = 0:
    ans = (n//2)*(n-1)
else:
    ans = ((n-1)//2)*n
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
if n%2 == 0:
    ans = (n//2)*(n-1)
else:
    ans = ((n-1)//2)*n
print(ans)
import heapq
from itertools import product
def resolve():
    n, m = map(int, input().split())
    cakes = [list(map(int, input().split())) for _ in range(n)]

    ans = 0

    for i in product([1, -1], repeat=3):
        hq = []
        heapq.heapify(hq)
        for x, y, z in cakes:
            point = i[0] * x + i[1] * y + i[2] * z
            if len(hq) != m:
                heapq.heappush(hq, point)
            elif hq[0] < point:
                heapq.heapreplace(hq, point)

        ans = max(ans, sum(hq))

    print(ans)
    
resolve()

### FIXED CODE ###

import heapq
from itertools import product
def resolve():
    n, m = map(int, input().split())
    cakes = [list(map(int, input().split())) for _ in range(n)]

    ans = 0

    if m == 0:
        print(0)
        return 

    for i in product([1, -1], repeat=3):
        hq = []
        heapq.heapify(hq)
        for x, y, z in cakes:
            point = i[0] * x + i[1] * y + i[2] * z
            if len(hq) != m:
                heapq.heappush(hq, point)
            elif hq[0] < point:
                heapq.heapreplace(hq, point)

        ans = max(ans, sum(hq))

    print(ans)
    
resolve()
n=int(input())
list=[]
for num in range(n):
    i=int(input())
    list.append(i)
for num in range(n):
    print(list.index(num+1)+1,end=" ")

### FIXED CODE ###

n=int(input())
a=[0]*n
l =list(map(int, input().split()))
for i in range(n):
    a[l[i]-1]=i+1
for i in range(n):
    print(a[i])
n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 1:
        print(-1)
        exit()
    else:
        print(max(0,inputs[0][1]))
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        elif s == 1 and c == 0:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
        

### FIXED CODE ###

n,m= map(int,input().split())
inputs = []
for _ in range(m):
    inputs.append(list(map(int,input().split())))

if m == 0:
    if n == 1:
        print(0)
    else:
        print(10**(n-1))
    exit()
elif n == 1:
    if len([i[1] for i in inputs if i[1] != inputs[0][1]]) > 0:
        print(-1)    
    else:
        print(max(0,inputs[0][1]))
    exit()
else:
    out = [-1] * n
    for item in inputs:
        s = item[0]
        c = item[1]
        if out[s-1] != -1 and out[s-1] != c:
            print(-1)
            exit()
        elif s == 1 and c == 0:
            print(-1)
            exit()
        else:
            out[s-1] = c

out[0] = max(out[0],1)
res = 0
for i in range(len(out)):
    if out[i] != -1:
        res += out[i] * 10 ** (n-i-1)
print(res)
a,b = [int(i) for i in input().split(' ')]
n=b-a#13-8=5
N=n-1#5-1=4
x=(1/2*N)*(N+1)#2*5=10
y= x - a#10-8=2
print(int(y))

### FIXED CODE ###

a = int(input())
if a>=1000:
    print("ABD")
else:
    print("ABC")
N, W = map( int, input().split())
dp = [0]*(W+1)
for _ in range(N):
    w, v = map( int, input().split())
    for i in range(W,-1,-1):
        if i >= w:
            dp[i] = max( dp[i], dp[i-w]+v)
        else:
            continue
print(dp[-1])

### FIXED CODE ###

from itertools import accumulate
N, W = map( int, input().split())
o, k = map( int, input().split())
A = [k]
B, C, D = [], [], []
for _ in range(N-1):
    w, v = map( int, input().split())
    if w == o:
        A.append(v)
    elif w == o+1:
        B.append(v)
    elif w == o+2:
        C.append(v)
    else:
        D.append(v)
A.sort(key=None, reverse = True)
B.sort(key=None, reverse = True)
C.sort(key=None, reverse = True)
D.sort(key=None, reverse = True)
A = [0] + list(accumulate(A))
B = [0] + list(accumulate(B))
C = [0] + list(accumulate(C))
D = [0] + list(accumulate(D))
# print(A)
# print(B)
# print(C)
# print(D)
ans = 0
for i in range( len(A)):
    for j in range( len(B)):
        for k in range( len(C)):
            for l in range( len(D)):
                if i*o + j*(o+1) + k*(o+2) + l*(o+3) <= W:
#                    print('{} {} {} {}'.format(i,j,k,l))
                    ans = max( ans, A[i]+B[j]+C[k]+D[l])
print(ans)
a,b,c = map(int,input().split())
if a+b>c and a+c>b and b+c>a:
  if a=b=c:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

a,b,c = map(int,input().split())
if a+b>c and a+c>b and b+c>a:
  if a==b==c:
    print('Yes')
  else:
    print('No')
def dfs(v):
    seen[v] = 1
    ans[v] += counter[v]

    for next_v in graph[v]:
        if seen[next_v]: continue
        ans[next_v] += ans[v]
        dfs(next_v)

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

graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

counter = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    counter[p-1] += x

seen = [0] * n
ans = [0] * n
dfs(0)

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from queue import Queue

n, q = map(int, input().split())
nodes = [[] for _ in range(n)]  # 隣接ノード
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    nodes[a].append(b)
    nodes[b].append(a)

counts = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    counts[p-1] += x

ans = [0] * n
ans[0] = counts[0]
done = [0] * n
queue = Queue()
queue.put(0)
while True:
    node = queue.get()
    done[node] = 1
    next_nodes = nodes[node]
    for next_node in next_nodes:
        if not done[next_node]:
            queue.put(next_node)
            ans[next_node] = ans[node] + counts[next_node]
    if queue.empty():
        break

print(*ans)
from collections import defaultdict
s=input()
K=int(input())


def calc(s, K):
    a = defaultdict(list)
    for i, c in enumerate(s):
        a[c].append(i)
    result = set()
    for i in range(ord('a'), ord('z')+1):
        for j in a[chr(i)]:
            for l in range(min(K, len(s[j:]))):
                result.add(s[j:j+l+1])
        if len(result) >= K:
            return sorted(list(result))[K-1]

print(calc(s, K))


### FIXED CODE ###

a, b, c, d = [int(i) for i in input().split()]

if (abs(a-b) <= d and abs(b-c) <= d) or abs(a-c) <= d:
    print('Yes')
else:
    print('No')
import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)

w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])

print(dp[N,-1])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=int)

w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])

print(dp[N,-1])
N, L=map(int, input().split())
if L>0:
    A=(N-1)*L+N*(N-1)/2
elif N+L<=0:
    A=(N-1)*L+(N-1)*(N-2)/2
else:
    A=(L*2+N-1)*N/2
print(int(A))

### FIXED CODE ###

S=int(input())
a=int(S/1000)
b=int((S-a*1000)/100)
c=int((S-a*1000-b*100)/10)
d=int(S-a*1000-b*100-c*10)
if a==b or b==c or c==d:
    print('Bad')
else:
    print('Good')
import sys
 
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)
 
def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)
 
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
 
dfs(0)
 
zerocnt = len(nums[0])
 
# if len(even) <= zerocnt:
#     for even_node in even:
#         ans[even_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for odd_node in odd:
#         ans[odd_node] = rest.pop()
 
# elif len(odd) <= zerocnt:
#     for odd_node in odd:
#         ans[odd_node] = nums[0].pop()
#     rest = nums[0] + nums[1] + nums[2]
#     for even_node in even:
#         ans[even_node] = rest.pop()
 
# len
# nums[1] >= nums[2] >= nums[0] >= nums[1]-1
# else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()
 
print(*ans)

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10 ** 6)
n = int(input())
 
edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)
 
def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)
 
for i in range(n-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
 
dfs(0)
 
zerocnt = len(nums[0])
 
if len(even) <= zerocnt:
    for even_node in even:
        ans[even_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for odd_node in odd:
        ans[odd_node] = rest.pop()
 
elif len(odd) <= zerocnt:
    for odd_node in odd:
        ans[odd_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for even_node in even:
        ans[even_node] = rest.pop()
 

else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()
 
print(*ans)
N, W = map(int, input().split())

import math
MAX = 10**5 + 1
dp = [[math.inf] * MAX for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MAX):
        if j < v:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)


### FIXED CODE ###

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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[i][:v] = dp[i-1][:v]
    dp[i][v:] = np.minimum(dp[i-1][v:], dp[i-1][:-v] + w)

ans = np.where(dp[N] <= W)[0].max()

print(ans)
a,b=input().split()
a=int(a)
b=int(b)
if ((a+b)%3)==0:
  print("Possible")
else:
  if (a%3)==0:
    print("Possible")
  else:
    if (b%3)==0:
      print("Possible")
      else:
        print("Impossible")

### FIXED CODE ###

a,b=input().split()
a=int(a)
b=int(b)
if ((a+b)%3)==0:
  print("Possible")
else:
  if (a%3)==0:
    print("Possible")
  else:
    if (b%3)==0:
      print("Possible")
    else:
      print("Impossible")
X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p = sorted(p)
q = sorted(q)
r = sorted(r)
P = A - X
Q = B - Y
R = C - 1
found = True
for i in range(C+1):
    if R < 0:
        break
    if P < A:
        if (r[C-i-1] >= p[P]):
            if (q[Q] >= p[P]):
                P += 1
                R -= 1
            elif r[C-i-1] > q[Q]:
                Q += 1
                R -= 1
            else:
                break
        elif Q < B:
            if r[C-i-1] > q[Q]:
                Q += 1
                R -= 1
            else:
                break
        else:
            break
    elif Q < B:
        if r[C-i-1] > q[Q]:
                Q += 1
                R -= 1
        else:
            break    
    else:
        break
print(sum(p[P:])+sum(q[Q:])+sum(r[R+1:]))

### FIXED CODE ###

X,Y,A,B,C = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
r = list(map(int,input().split()))
p = sorted(p)
q = sorted(q)
r = sorted(r)
P = A - X
Q = B - Y
R = C - 1
found = True
for i in range(C+1):
    if R < 0:
        break
    if P < A:
        if (r[C-i-1] >= p[P]):
            if Q < B:
                if (q[Q] >= p[P]):
                    P += 1
                    R -= 1
                elif r[C-i-1] > q[Q]:
                    Q += 1
                    R -= 1
                else:
                    break
            else:
                P += 1
                R -= 1
        elif Q < B:
            if r[C-i-1] > q[Q]:
                Q += 1
                R -= 1
            else:
                break
        else:
            break
    elif Q < B:
        if r[C-i-1] > q[Q]:
            Q += 1
            R -= 1
        else:
            break    
    else:
        break
print(sum(p[P:])+sum(q[Q:])+sum(r[R+1:]))
import re

def checkFunction(c):
    # print(c)
    c = re.sub('^R+','',c)
    if (not 'WR' in c):
        return 0
    if c.index('R') + 1 != len(c):
        c2 = c.replace('WR', 'RR',1)[:-1]
        return checkFunction(c2) + 1
    return 1


N = int(input())
c= input()

print(checkFunction(c))


### FIXED CODE ###


def check(N, c):
    RinRight = c.count('R')
    WinLeft = 0
    r = RinRight
    for i in range(N):
        if c[i] == 'R':
            RinRight -= 1
        else: # c[i] == 'W'
            WinLeft +=1
        r = min(r, max(RinRight,WinLeft))

    return r


N = int(input())
c= input()
print(check(N,c))
N, K = map(int, input().split())
S = str(input())
S_list = []
cum_list = [0]
tmp = 1
count = 0
if "0" not in S:
    print(len(S))
else:
    for i in range(N):
        if i == 0:
            if int(S[i]) == tmp:
                count += 1
            else:
                S_list.append(count)
                count = 1
        else:
            if S[i] == S[i - 1]:
                count += 1
                if i == N - 1:
                    S_list.append(count)
            else:
                S_list.append(count)
                count = 1


    if S[-1] == "0":
        S_list.append(0)




    now = 0
    for i in range(len(S_list)):
        now += S_list[i]
        cum_list.append(now)
    def check(x,K):
        answer_list = []
        i = 0
        if i + 2 * K + 1 < len(x):
            while i + 2 * K + 1 < len(x):
                answer_list.append(x[i + 2 * K + 1] - x[i])
                i += 2
            return answer_list
        elif K > 0:
            check(x,K-1)
    answer_list = check(cum_list,K)

    answer = max(answer_list)
    print(answer)

### FIXED CODE ###

N, K = map(int, input().split())
S = str(input())
S_list = []
cum_list = [0]
tmp = 1
count = 0

for i in range(N):
    if i == 0:
        if int(S[i]) == tmp:
             count += 1
        else:
            S_list.append(count)
            count = 1
    else:
        if S[i] == S[i - 1]:
            count += 1
            
        else:
            S_list.append(count)
            count = 1

S_list.append(count)
if S[-1] == "0":
    S_list.append(0)


now = 0
for i in range(len(S_list)):
    now += S_list[i]
    cum_list.append(now)


answer_list = []
i = 0
if 2 * K + 1 < len(cum_list):
    while i + 2 * K + 1 < len(cum_list):
        answer_list.append(cum_list[i + 2 * K + 1] - cum_list[i])
        i += 2
else:
    answer_list.append(len(S))
answer = max(answer_list)
print(answer)