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

import math
n, m = map(int,input().split(' '))
d = list(map(int,input().split(' ')))
d.sort()
inf = n

dp = [ [ inf for i in range(m+1)] for j in range(n+1) ]

# dp
for j in range(m+1):
    dp[0][j]=0

for j in range(m-1,-1,-1):
    for i in range(n+1):
        for k in range(math.floor(i/d[j])+1 ):
            r = (k)*d[j]
            #print(i,j,k)
            dp[i][j] = min( dp[i][j], min( dp[i][j+1], dp[i-r][j]+k) )

print(dp[n][0])



### FIXED CODE ###

import math
n, m = map(int,input().split(' '))
d = list(map(int,input().split(' ')))
d.sort()
inf = n

dp = [ [ inf for i in range(m+1)] for j in range(n+1) ]

# dp
for j in range(m+1):
    dp[0][j]=0

for j in range(m-1,-1,-1):
    for i in range(n+1):
        #for k in range(math.floor(i/d[j])+1):
        if math.floor(i/d[j]) >=1:
            k=1
        else:
            k=0
        r = k*d[j]
        #print(i,j,k)
        dp[i][j] = min( dp[i][j], dp[i][j+1], dp[i-r][j]+k ) 
        #print("dp:",i,j,dp[i][j])
print(dp[n][0])
### BUGGY CODE ###

import math
    
def isprime(x):
    p = [2]
    if x == 2:
        return True
    if x == 3:
        return True
    if max(p) < x**0.5:
        for j in range(max(p), math.floor(x**0.5) + 1):
            if all([j % k != 0 for k in p]):
                p.append(j)
    i = 0
    while i <= len(p)-1:
        if p[i] > x**0.5:
            return False
        if x%p[i] == 0:
            return False
        i += 1
    return True


n = int(input())
res = 0
for i in range(n):
    k = int(input())
    if isprime(k):
        res += 1
print(res)

### FIXED CODE ###

import math

p = [2]
    
def isprime(x):
    if x == 2:
        return True
    if x == 3:
        return True
    if max(p) < x**0.5:
        for j in range(max(p), math.floor(x**0.5) + 1):
            if all([j % k != 0 for k in p]):
                p.append(j)
    i = 0
    while i <= len(p)-1:
        if x%p[i] == 0:
            return False
        if p[i] > x**0.5:
            break;
        i += 1
    return True


n = int(input())
res = 0
for i in range(n):
    k = int(input())
    if isprime(k):
        res += 1
print(res)
### BUGGY CODE ###

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
X=[[[0,0] for _ in range((H*W)//D+1)] for _ in range(D)]
for i in range(H):
    for j in range(W):
        X[A[i][j]%D][A[i][j]//D][0]=i
        X[A[i][j]%D][A[i][j]//D][1]=j

for i in range(Q):
    L,R=map(int,input().split())
    ans=0
    for j in range(L//D,R//D):
        ans+=abs(X[L%D][j][0]-X[L%D][j+1][0])+abs(X[L%D][j][1]-X[L%D][j+1][1])
    print(ans)

### FIXED CODE ###

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
X=[[[0,0] for _ in range((H*W)//D+1)] for _ in range(D)]
for i in range(H):
    for j in range(W):
        X[A[i][j]%D][A[i][j]//D][0]=i
        X[A[i][j]%D][A[i][j]//D][1]=j
M=[[0] for _ in range(D)]
for d in range(D):
    for k in range((H*W)//D):
        M[d].append(abs(X[d][k+1][0]-X[d][k][0])+abs(X[d][k+1][1]-X[d][k][1])+M[d][k])

for i in range(Q):
    L,R=map(int,input().split())
    print(M[L%D][R//D]-M[L%D][L//D])
### BUGGY CODE ###

s = input()
count = 0
while 'ABC' in s:
        count += s.count('ABC')
        s = s.replace('ABC',"BCA")
print(count)

### FIXED CODE ###

a = input()
b = []
count = 0
a = a.replace('BC','D')
for i in range(1,len(a)+1):
    if a[-i] == 'D':
        count += 1
    elif a[-i] == 'A':
        b.append(count)
    else:
        count = 0
print(sum(b))
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        y *= i
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
def comb(n, r, mod):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    for i in range(1, r+1):
        x *= n+1-i
        x %= mod
        y *= i
        y %= mod
    return x*pow(y, mod-2, mod)%mod

ans = (pow(2, n, mod)+3*mod-1-comb(n, a, mod)-comb(n, b, mod))%mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = {}
for i in range(n):
  c[a[i]] = c.get(a[i], 0) + 1
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)



### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
max_ = max(a)+1
prime_bool = [True]*max_
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p < max_:
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)
### BUGGY CODE ###

from numpy.linalg import solve
n = int(input())
a = list(map(int,input().split()))
l = [[0 for j in range(n)] for _ in range(n)]

for i in range(n):
	if i != n-1:
		l[i][i], l[i][i+1] = 1/2, 1/2
	else:
		l[i][0], l[i][i] = 1/2, 1/2

left = l
right = a

ans = solve(left,right)
print(" ".join(list(map(str,list(map(int,ans))))))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
y = [0 for _ in range(n)]
suma = sum(a)
ans = []
memo1 = 2*sum([a[j%n] for j in range(0, 0+n, 2)])-suma
memo2 = 2*sum([a[j%n] for j in range(1, 1+n, 2)])-suma
ans.append(str(memo1))
ans.append(str(memo2))
# (i+n-2)%n - (i-2)%n
for i in range(2,n):
	if i%2 == 0:
		memo1 = memo1 + 2*(a[(i+n-1)%n] - a[(i-2)%n])
		ans.append(str(memo1))
	else:
		memo2 = memo2 + 2*(a[(i+n-1)%n] - a[(i-2)%n])
		ans.append(str(memo2))
print(" ".join(ans))
### BUGGY CODE ###

import sys
i=0
L=list(input())
N=len(L)
if N==1:
  print(0)
  sys.exit()
for j in range(N):
  i=0
  S=len(L)
  if S==1 or S==0:
    break
  while True:
    if L[i]!=L[i+1]:
      L.pop(i)
      L.pop(i)
      if L==[]:
        print(N)
        sys.exit()
    i+=1
    if i>len(L)-2:
      break
  if S==len(L):
    break
print(N-len(L))

### FIXED CODE ###

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

N,Q=map(int, input().split())
S=list(input())
A = []
for i in range(Q):
  A.append(list(map(int, input().split())))
flag=0
B = []
for i in range(N):
  if S[i]=="A":
    flag=i
    continue
  if S[i]=="C" and flag==i-1:
    B.append(i)
    flag=False
for i in range(Q):
  print(sum(A[i][0]<=x<A[i][1] for x in B))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
a=[0]*N
for i in range(N-1):
  a[i+1]=a[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])
### BUGGY CODE ###

numbers = input()
position = int(input())
roop = True
while roop:
    new_number = ""
    if len(numbers) > position:
        numbers = numbers[:position]
    for num in numbers:
        for i in range(1, 10):
            if num == str(i):
                new_number += str(i) * i
    if (numbers != new_number[:position]):
        numbers = new_number[:position]
    else:
        roop = False
print(numbers[position - 1: position])


### FIXED CODE ###

numbers = input()
position = int(input())
answer = "1"
for num in numbers[:position]:
    if num != "1":
        answer = num
        break
print(answer)
### BUGGY CODE ###

def main():
  def prime_factorize(n):
    a = []
    while n % 2 == 0:
      a.append(2)
      n //= 2
    f = 3
    while f * f <= n:
      if n % f == 0:
        a.append(f)
        n //= f
      else:
        f += 2
    if n != 1:
      a.append(n)
    return a
  def prime_dict(a):
    import collections
    c = collections.Counter(prime_factorize(a))
    return c

  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  c = {}
  for i in a:
    d = prime_dict(i)
    for k in d.keys():
      m = 0
      if k in c:
        m = c[k]
      c[k] = max(d[k],m)
  lcm = 1
  for k,v in c.items():
    lcm *= k**v
  for i in a:
    ans += lcm//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N=int(input())
G=[list() for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも

def dijkstra(o):
    d=[float('inf') for i in range(N)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(N)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev

Q,K=map(int,input().split())
d=dijkstra(K-1)[0]
for i in range(Q):
    x,y=map(int,input().split())
    print(d[x-1]+d[y-1])



### FIXED CODE ###

from collections import deque
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N=int(input())
G=[list() for i in range(N)]
P=[False for i in range(N)]
A=[-100 for i in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) #無向グラフならこれも



def solve(G,K,P):
    q=deque()
    q.append(K)
    while q:
        s=q.pop()
        for i in G[s]:
            if(P[i.to]):
                continue
            P[i.to]=True
            A[i.to]=A[s]+i.cost
            q.append(i.to)

Q,K=map(int,input().split())
A[K-1]=0
P[K-1]=True
solve(G,K-1,P)


for i in range(Q):
    x,y=map(int,input().split())
    
    print(A[x-1]+A[y-1])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l=sorted(l,reverse=True)

anset=set()


for i in range(n-2):
  flag=False
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        temp=""
        temp+=str(l[i])+str(l[j])+str(l[k])
        #print(temp)
        anset.add(temp)
      else:#それ以降のj,kで三角形作れるのは無いので最初のfor文に戻る
        flag=True
    if flag==True:
      break

#ansetの長さを出力
print(len(anset))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()

import bisect

ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ind=bisect.bisect_left(l,l[i]+l[j])
    ans+=ind-j-1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mp = {}
for i in range(n):
    mp[a[i]] = a[i]
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
    print(sum(a[:]))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mp, ans = {}, 0
for i in range(n):
    if(a[i] in mp.keys()):
        mp[a[i]] += 1
    else:
        mp[a[i]] = 1
for k in mp.keys():
    ans += k * mp[k]
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if(b not in mp.keys()):
        mp[b] = 0
        print(ans)
        continue
    if(c in mp.keys()):
        mp[c] += mp[b]
    else:
        mp[c] = mp[b]
    ans += (c-b) * mp[b]
    mp[b] = 0
    print(ans)
### BUGGY CODE ###

import bisect
import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=sorted(list(map(int,input().split())))
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  l=bisect.bisect_left(A,b)
  r=bisect.bisect_right(A,b)
  for j in range(l,r):
    A[j]=c
  print(sum(A))


### FIXED CODE ###

import sys

def input():
  return sys.stdin.readline()

N=int(input())
A=list(map(int,input().split()))
B=[0]*(10**5)
for a in A:
  B[a-1]+=1
s=sum(A)
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  bb,bc=B[b-1],B[c-1]
  B[c-1]+=bb
  B[b-1]=0
  s+=bb*c-bb*b
  print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import math
# スペース区切りの整数の入力
X, K, D = map(int, input().split())

cross = abs(-(-X//D))

if cross >= K:
    for i in range(K):
        if X >= 0:
            X -= D
        else:
            X += D
    print(abs(X))
else:
    for i in range(cross):
        if X >= 0:
            X -= D
        else:
            X += D
    
    if (K-cross)%2 == 0:
        print(abs(X))
    else:
        if X >= 0:
            print(abs(X-D))
        else:
            print(abs(X+D))





### FIXED CODE ###

#!/usr/bin/env python3
import math
# スペース区切りの整数の入力
X, K, D = map(int, input().split())

cross = abs(-(-X//D))

if cross >= K:
    if X >= 0:
        X -= D*K
    else:
        X += D*K
    print(abs(X))
else:
    if X >= 0:
        X -= D*cross
    else:
        X += D*cross
    
    if (K-cross)%2 == 0:
        print(abs(X))
    else:
        if X >= 0:
            print(abs(X-D))
        else:
            print(abs(X+D))
### BUGGY CODE ###

def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    # number = 635
    # dists = [1] * number
    # operations = number
    satulation = any((
        operations >= 40,
        number <= 3000 and operations >= 25,
        number <= 1000 and operations >= 21,
        number <= 625 and operations >= 20,
    ))
    if satulation:
        print(*([number] * number))
        return

    for xx in range(operations):
        dists_new = [0] * number
        min_d = number
        for i, d in enumerate(dists):
            min_d = min(d, min_d)
            start = max(0, i - d)
            end = min(i + d, number - 1)
            for j in range(start, end + 1):
                dists_new[j] += 1
        dists = dists_new
        if min_d == number:
            # すべての光が両端まで届く，変化しなくなる。
            # print('Over', xx)
            break

    print(*dists)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def main():
    number, operations = [int(x) for x in input().split()]
    dists = [int(x) for x in input().split()]

    for ope_count in range(operations):
        temp = [0] * (number + 1)
        for i, v in enumerate(dists):
            left = max(i - v, 0)
            right = min(i + v + 1, number)
            temp[left] += 1
            temp[right] -= 1
        templi = list(accumulate(temp))
        if templi == dists:
            break
        else:
            dists = templi

    print(*list(dists)[:-1])


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

# -*- coding: utf-8 -*-
from itertools import permutations
def inpl(): return tuple(map(int, input().split()))
 
INF = float("inf")
 
N, M, _ = inpl()
R = inpl()
G = [[INF]*(N+1) for _ in range(N+1)]

for _ in range(M):
    s, t, d = inpl()
    G[s][t] = d
    G[t][s] = d

for v in range(N):
    G[v][v] = 0 

def WarshallFloyd(G):
    V = len(G)
    for k in range(V):
        for i in range(V):
            if G[i][k] == INF:
                continue
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

G = WarshallFloyd(G)

res = INF
for r in permutations(R, len(R)):
    tmp = 0
    for i in range(len(R)-1):
        tmp += G[r[i]][r[i+1]]
    res = min(res, tmp)
 
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

for i ,j, k in product(range(1, N+1), repeat=3):
    G[j][k] = min(G[j][k], G[j][i] + G[i][k])

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

counter = 0

for i, s1 in enumerate(S):
    #rgb = [f]
    for j, s2 in enumerate(S[i+1:]):
        if s1 == s2:
            continue
        else:
            d = j+1
            #print(d)
            #print(S[i+j+2:])
            for k, s3 in enumerate(S[i+j+2:]):
                if s3 != s1 and s3 != s2 and d != k+1:
                    counter += 1
print(counter)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N):
    for j in range(i+1,N):
        k = 2*j-i
        if N > k and S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
sum_w = s.count("W")
ans = n
for i in range(n):
    left_w = s[:i].count("W")
    right_e = (n-i-1)-(sum_w-left_w)
    if s[i] == "W":
        right_e += 1
    sum = left_w+right_e
    if sum < ans:
        ans = sum
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
sum_w = s.count("W")
ans = n
lw = [0]*n
count = 0
for i in range(n):
    lw[i] = count
    if s[i] == "W":
        count += 1
for i in range(n):
    left_w = lw[i]
    right_w = sum_w-left_w
    if s[i] == "W":
        right_w -= 1
    right_e = (n-i-1)-right_w
    sum = left_w+right_e
    if sum < ans:
        ans = sum
print(ans)
### BUGGY CODE ###

K = int(input())

import math
from functools import reduce

sum = 3*(K-1)*(K-1) + 3*(K-1) + 1

for i in range(2, K + 1):
    for j in range(2, K + 1):
        for k in range(2, K + 1):
            sum += math.gcd(math.gcd(i,j),k)

print(sum)

### FIXED CODE ###

K = int(input())

import math
from functools import reduce

sum = 3*(K-1)*(K-1) + 3*(K-1) + 1

for i in range(2, K + 1):
    for j in range(2, K + 1):
        for k in range(2, K + 1):
            sum += math.gcd(math.gcd(i,j),k)

print(sum)
### BUGGY CODE ###

from collections import deque
s = deque(input())
lsts = deque()

for i in range(len(s)):
  s[i] = int(s[i])
cou = 0

for i in range(100):
  lsts = deque(s)
  l = 2019*(i+1)
  llen = len(str(l))
  
  for j in range(len(s)-llen+1):
    st = 0
    
    for k in range(llen):
      st += lsts[-(1+k)] * (10**k)
      
    lsts.pop()
    if st == l:
      cou += 1

print(cou)

### FIXED CODE ###

from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st += int(i) * kai
  st %= 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10 % 2019

print(cou)
### BUGGY CODE ###

L,R=map(int,input().split())
if L-R>=2019:
    print(0)
else:
    x=[i*j%2019 for i in range(L,R) for j in range(i+1,R+1)]
    print(min(x))

### FIXED CODE ###

L,R=map(int,input().split())
if R-L>=2019:
    print(0)
else:
    x=[i*j%2019 for i in range(L,R) for j in range(i+1,R+1)]
    print(min(x))
### BUGGY CODE ###

N=int(input())
x=[]
min=10000000
ans=0
for i in range(1,N+1):
  if N%i==0:
    j=int(N/i)
    a=[i,j]
    x.append(a)
for i,j in x:
  if i+j<=min:
    ans=i+j-2
    min=i+j
print(ans)


### FIXED CODE ###

import math
N=int(input())
x=[]
min=10000000000000000
ans=0
sqN=math.ceil(math.sqrt(N))
for i in range(1,sqN+1):
  if N%i==0:
    j=int(N/i)
    a=[i,j]
    x.append(a)
for i,j in x:
  if i+j<=min:
    ans=i+j-2
    min=i+j
print(ans)
### BUGGY CODE ###

h,w,m = map(int,input().split())
t = list(list(map(int,input().split())) for _ in range(m))

ans = 0

for i in range(h):
  for j in range(w):
    n = [l[0] for l in t].count(i+1) +  [l[1] for l in t].count(j+1)
    if [i+1,j+1] in t:
      n -= 1
    if n > ans:
      ans = n
      
print(ans)

### FIXED CODE ###

import numpy as np

h,w,m = map(int,input().split())
t = list(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m))

H = [0] * h
W = [0] * w
for x,y in t:
    H[x] += 1
    W[y] += 1
H_max = max(H)
W_max = max(W)

H_index = [x for x,i in enumerate(H) if i == H_max]
W_index = [y for y,j in enumerate(W) if j == W_max]

ans = H_max + W_max

t = set(t)
for r in H_index:
    for c in W_index:
        if (r, c) not in t:
            print(ans)
            exit()
print(ans - 1)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
if(N<=K):
	print(0)
	exit()
H.sort(reverse=True)
for i in range(K):
	H.pop(0)
print(sum(H))

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
if(N<=K):
	print(0)
	exit()
H.sort(reverse=True)
print(sum(H[K:]))
### BUGGY CODE ###

import fractions
from functools import reduce
def gcd(i):
    return reduce(fractions.gcd, i)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    tmp = 0
    if gcd(A) == max(A):
        print(gcd(A))
        exit()
    else:
        for i in range(N):
            if i == 0 :
                tmp=max(tmp,gcd(A[1:]))
            elif i == N-1:
                tmp=max(tmp,gcd(A[:N-1]))
            else:
                tmp=max(tmp,gcd(A[:i]+A[i+1:]))
    print(tmp)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import fractions
from functools import reduce
def gcd(*i):
    return reduce(fractions.gcd, i)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L=[0]
    R=[0]
    for i in range(N):
        L.append(gcd(L[i],A[i]))
        R.append(gcd(R[i],A[-(i+1)]))
    R=R[::-1]
    ans=[]
    for i in range(N):
        ans.append(gcd(L[i],R[i+1]))
    print(max(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 0
for idx, s in enumerate(S[:-1]):
    count += 1
    if s != S[idx+1]:
        S_list.append(count)
        count = 0

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

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        ans = max(ans, sum(S_list[left:right+1]))
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
S += "#"
S_list = []
if S[0] == "0":
    S_list.append(0)

count = 1
before_s = S[0]
for s in S[1:]:
    count += 1
    if before_s != s:
        S_list.append(count-1)
        count = 1
    before_s = s

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

# print(S_list)

if len(S_list) < 2 * K:
    print(sum(S_list))
else:
    ans = 0
    ans_list = []
    for i in range(0, len(S_list) - (2 * K), 2):
        left = i
        right = i + 2 * K
        # print(S_list[left:right+1])
        if i == 0:
            ans = sum(S_list[left:right+1])
            ans_list.append(ans)
        else:
            # print(S_list[left-2:left], S_list[right-1:right+1])
            ans = ans - sum(S_list[left-2:left]) + sum(S_list[right-1:right+1])
            ans_list.append(ans)
    print(max(ans_list))