Harryxun/stf_run huggingface dataset:
def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # 初期値dp[0][W] = 0の価値(もし0の重さがMAXを超えるなら選べない)
    dp = [[0]*(W+1) for i in range(N)]
    for x in range(W+1):
        dp[0][x] = 0 if w[0]>x else v[0]
    for i in range(N-1):
        for j in range(W+1):
            if w[i+1]<=j:
                # i+1番目を選ぶ
                dp[i+1][j] = max(dp[i+1][j], (dp[i][j-w[i+1]])+v[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    print(dp[-1][W])

main()


### FIXED CODE ###

def main():
    N,W = map(int, input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int, input().split())
    # dp[i][w] := 容量をwとして荷物0~iの中から荷物を選んだ時の価値の最大値
    # ではなく...
    # dp[i][v] := 荷物0~iの中から荷物を選んで価値vを超える時の重さ合計の最小値
    # 初期値dp[0][v] = 0の重さ(もし0の価値がvを超えないならINF)
    V = N*max(v)
    INF = float('inf')
    dp = [[INF]*(V+1) for i in range(N)]
    for x in range(V+1):
        dp[0][x] = INF if x>v[0] else w[0]
    dp[0][0] = 0
    for i in range(N-1):
        for j in range(V+1):
            if j>=v[i+1]:
                # i+1番目を選ぶ
                dp[i+1][j] = min(dp[i+1][j], (dp[i][j-v[i+1]])+w[i+1])
            # i+1番目を選ばない
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])

    # dp[N-1]のうちW以下であるものの価値の最大値
    for val in range(V,-1,-1):
        if dp[-1][val]<=W:
            print(val)
            break
main()
import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(1, n+1)}
sizes = {i:1 for i in range(1, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, a):
	if parent[a] != a: parent[a] = f(parent, parent[a])
	return parent[a]

for a,b in friendships:
	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		parent[pb] = pa
		sizes[pa] += sizes[pb]

for c,d in disses:
	pa,pb = f(parent, c), f(parent, d)
	if (d not in adj[c]) and  (pa == pb):
		hd[c] += 1
		hd[d] += 1

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])

### FIXED CODE ###

import collections

n,m,k = map(int,raw_input().split(' '))

friendships = [map(int, raw_input().split(' ')) for _ in range(m)]
disses = [map(int, raw_input().split(' ')) for _ in range(k)]

parent = {i:i for i in range(0, n+1)}
sizes = {i:1 for i in range(0, n+1)}

hd = collections.Counter()

adj = collections.defaultdict(set)

def f(parent, u):
	if parent[u] != u: 
		parent[u] = f(parent, parent[u])
	return parent[u]

for a,b in friendships:
	if a == b: continue

	pa,pb = f(parent, a), f(parent, b)
	
	adj[a].add(b)
	adj[b].add(a)

	if pa != pb:
		if sizes[pa] >= sizes[pb]:
			parent[pb] = pa
			sizes[pa] += sizes[pb]
		else:
			parent[pa] = pb
			sizes[pb] += sizes[pa]

for c,d in disses:
	pc,pd = f(parent, c), f(parent, d)
	if (pc == pd):
		hd[c] += 1
		hd[d] += 1
"""
hd[u] = k
u has k disses in its connected component
"""

print ' '.join([str(sizes[f(parent,u)] - len(adj[u]) - hd[u] - 1)  for u in range(1, n+1)])
X,Y,Z = map(int,input().split())
ans = (X-Z)//(Y+Z)
print(ans)


### FIXED CODE ###

x,y=input().split()
if x > y:
  print(">")
elif x==y:
  print("=")
else:
  print("<")
N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s += ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
a = [0]+[int(i) for i in input().split()]
ret = [0] * (N+1)

def rec(i) :
    if i == N + 1 :
        return
    rec(i+1)
    s = 0
    for j in range(i, N + 1, i) :
        s ^= ret[j]
    ret[i] = s^a[i]
    
rec(1)
b = []
for i in range(1, N + 1) :
    if ret[i] :
        b.append(str(i))
print(len(b))
print(' '.join(b))
N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
same_roads = {}
same_rails = {}

max_road_id = -1
for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  if roads[p] < 0 and roads[q] < 0:
    max_road_id += 1
    roads[p] = max_road_id
    roads[q] = max_road_id
  elif roads[p] == roads[q]:
    continue
  elif roads[p] >= 0 and roads[q] < 0:
    roads[q] = roads[p]
  elif roads[q] < 0 and roads[q] >= 0:
    roads[p] = roads[q]
  else:
    same_roads[max(roads[p],roads[q])] = min(roads[p],roads[q]) 
distinct_roads = [i for i in range(max_road_id + 1)]
for road_id in range(max_road_id, -1, -1):
  if road_id in same_roads:
    distinct_roads[road_id] = same_roads[road_id]
 
max_rail_id = -1
for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  if rails[r] < 0 and rails[s] < 0:
    max_rail_id += 1
    rails[r] = max_rail_id
    rails[s] = max_rail_id
  elif rails[r] == rails[s]:
    continue
  elif rails[r] >= 0 and rails[s] < 0:
    rails[s] = rails[r]
  elif rails[r] < 0 and rails[s] >= 0:
    rails[r] = rails[s]
  else:
    same_rails[max(rails[r],rails[s])] = min(rails[r],rails[s])
distinct_rails = [i for i in range(max_rail_id + 1)]
for rail_id in range(max_rail_id, -1, -1):
  if rail_id in same_rails:
    distinct_rails[rail_id] = same_rails[rail_id]

combi_counts = {}
for i in range(N):
  road = roads[i]
  rail = rails[i]
  if road < 0 or rail < 0:
    continue
  if (road,rail) in combi_counts:
    combi_counts[(distinct_roads[road],distinct_rails[rail])] += 1
  else:
    combi_counts[(distinct_roads[road],distinct_rails[rail])] = 1

result = []
for i in range(N):
  road = roads[i]
  rail = rails[i]
  if road < 0 or rail < 0:
    result.append(1)
  else:
    result.append(combi_counts[(distinct_roads[road],distinct_rails[rail])])
print ' '.join(map(str, result))

### FIXED CODE ###

from collections import Counter
N,K,L = map(int,input().split())

p_road = [i for i in range(N)]
p_rail = [i for i in range(N)]

def root(a,par):
    if a == par[a]: return a
    par[a] = root(par[a],par)
    return par[a]

def unite(a,b,par):
    ra = root(a,par)
    rb = root(b,par)
    if ra == rb: return
    par[ra] = rb

for i in range(K):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_road)

for i in range(L):
    a,b = map(lambda x:int(x)-1, input().split())
    unite(a,b,p_rail)

road_ids = []
rail_ids = []
for i in range(N):
    road_ids.append(root(i,p_road))
    rail_ids.append(root(i,p_rail))

ctr = Counter()
for a,b in zip(road_ids, rail_ids):
    ctr.update([(a,b)])

print(' '.join(list(map(str, [ctr[(road_ids[i], rail_ids[i])] for i in range(N)]))))
n=int(input())
d=[]
for i in range(1, n+1)
  if i%3==0 or "3" in str(i):
    d.append(i)
print(' ', end="")
print(*d)


### FIXED CODE ###

n=int(input())
d=[]
for i in range(1,n+1):
    if i%3==0 or "3" in str(i):
        d.append(i)
print(" ",end="")
print(*d)
from collections import deque

s = input()

ns = ""

for s_i in s:
    if s_i != "x":
        ns += s_i

if ns != ns[::-1]:
    print(-1)
    exit()

if len(ns) % 2 == 1:
    cnt = -1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2:
            note = i
            break
    left = deque(s[:note][::-1] + "@")
    right = deque(s[note+1:] + "@")
else:
    cnt = -1
    f = 1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2 - 1 and f:
            l = i
            f = 0
        if cnt == len(ns)//2:
            r = i
            break
    left = deque(s[:l][::-1] + "@")
    right = deque(s[r+1:] + "@")

ans = 0

while left or right:
    print(left,right)
    if left[0] == right[0]:
        left.popleft()
        right.popleft()
    elif left[0] == "x":
        left.popleft()
        ans += 1
    elif right[0] == "x":
        right.popleft()
        ans += 1

print(ans)

### FIXED CODE ###

from collections import deque

s = input()

ns = ""

for s_i in s:
    if s_i != "x":
        ns += s_i

if ns != ns[::-1]:
    print(-1)
    exit()

if ns == "":
    print(0)
    exit()

if len(ns) % 2 == 1:
    cnt = -1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2:
            note = i
            break
    left = deque(s[:note][::-1] + "@")
    right = deque(s[note+1:] + "@")
else:
    cnt = -1
    f = 1
    for i,s_i in enumerate(s):
        if s_i != "x":
            cnt += 1
        if cnt == len(ns)//2 - 1 and f:
            l = i
            f = 0
        if cnt == len(ns)//2:
            r = i
            break
    left = deque(s[:l][::-1] + "@")
    right = deque(s[r+1:] + "@")

ans = 0

while left or right:
    if left[0] == right[0]:
        left.popleft()
        right.popleft()
    elif left[0] == "x":
        left.popleft()
        ans += 1
    elif right[0] == "x":
        right.popleft()
        ans += 1

print(ans)
n, m = input().split()
days = list(map(int, input().split()))
if n < sum(days):
  print("-1")
else:
  print(int(n) - sum(days))

### FIXED CODE ###

n, m = input().split()
days = list(map(int, input().split()))
if int(n) < sum(days):
  print("-1")
else:
  print(int(n) - sum(days))
import itertools
import math


def gcd(a,b):
    while b:
        a, b = b, a % b
    return a


def lcm(left, right):
    return (int(left) * int(right)) / int(gcd(left, right))


N = int(input().strip())
Ts = []
for i in range(N):
    Ts.append(int(input().strip()))

res = int(lcm(Ts[0], Ts[1]))
for T in Ts[2:]:
    res = int(lcm(res, T))

print(str(int(res)))

### FIXED CODE ###

import itertools
import math


def gcd(a,b):
    while b:
        a, b = b, a % b
    return a


def lcm(left, right):
    return (left * right) // gcd(left, right)


N = int(input().strip())
Ts = []
for i in range(N):
    Ts.append(int(input().strip()))

res = 0
if len(Ts) == 0:
    res = 0
elif len(Ts) == 1:
    res = Ts[0]
else:
    res = int(lcm(Ts[0], Ts[1]))
    for T in Ts[2:]:
        res = int(lcm(res, T))

print(str(int(res)))
n,m=map(int,input().split())
a=list(map(int,input().split()))

limit=sum(a)/(4*m)
c=0
for aa in a:
  if a >=limit:
    c+=1
  else:
    pass
if c==0:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
     
limit=sum(a)/(4*m)
c=0
for aa in a:
  if aa >=limit:
    c+=1
  else:
    pass
if c>=m:
  print('Yes')
else:
  print('No')
def available(start, end, S, step=None):
    if step is not None:    #   追い越し処理
        S = S[:step] + "#" + S[step+1:]
    for i in range(start-1, end-1):
        if S[i] == "#" and S[i+1] == "#":
            return False
    return True, S
    
def overtake(start, end, S):
    for i in range(start-1, end-1):
        if S[i-1] == "." and S[i] == "." and S[i+1] == ".":
            step = i
            return True, step
    return False, None

N, A, B, C, D = map(int, input().split())
S = input()

if D > C:   #   追い越しが不要な時
    judge1, S = available(A, C, S)
    judge2, S = available(B, D, S)
    if judge1 and judge2:
        print("Yes")
    else:
        print("No")
else:   #   追い越しが必要な時
    overtakable, step = overtake(B, D, S)
    if overtakable:   #   追い越しが可能な時
        judge1, S = available(A, C, S, step=step)
        judge2, S = available(B, D, S)
        if judge1 and judge2:
            print("Yes")
        else:
            print("No")
    else:   #   追い越しができない時
        print("No")
        

### FIXED CODE ###

def available(start, end, S, step=None):
    if step is not None:    #   追い越し処理
        S = S[:step] + "#" + S[step+1:]
    for i in range(start, end):
        if S[i] == "#" and S[i+1] == "#":
            return False, S
    return True, S
    
def overtake(start, end, S):
    for i in range(start, end+1):
        if S[i-1] == "." and S[i] == "." and S[i+1] == ".":
            step = i
            return True, step
    return False, None

N, A, B, C, D = map(int, input().split())
S = "." + input() + "."

if D > C:   #   追い越しが不要な時
    judge1, S = available(A, C, S)
    judge2, S = available(B, D, S)
    if judge1 and judge2:
        print("Yes")
    else:
        print("No")
else:   #   追い越しが必要な時
    overtakable, step = overtake(B, D, S)
    if overtakable:   #   追い越しが可能な時
        judge1, S = available(B, D, S)
        judge2, S = available(A, C, S, step=step)
        if judge1 and judge2:
            print("Yes")
        else:
            print("No")
    else:   #   追い越しができない時
        print("No")
import math
mod = 10**9 + 7
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
X, Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
n = (2*Y-X)//3
m = (2*X-Y)//3
print(C(n+m,m) % mod)

### FIXED CODE ###

MOD = 10**9 + 7
def comb(n, k, MOD):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    if k == 0:
        return 1
    iinv = [1] * (k + 1)
    ans = n
    for i in range(2, k + 1):
        iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
        ans *= (n + 1 - i) * iinv[i] % MOD
        ans %= MOD
    return ans
X, Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
n = (2*Y-X)//3
m = (2*X-Y)//3
print(comb(n+m,m,MOD))
from scipy.special import comb
N=int(input())
dic={}
ans=0
for i in range(N):
    s=list(input())
    s.sort()
    S=''.join(s)
    if S not in dic:
        dic[S]=1
    else:
        dic[S]+=1
for v in dic.values():
    if v>=2:
        ans+=int(comb(v,2))
print(dic)

### FIXED CODE ###

N=int(input())
dic={}
ans=0
for i in range(N):
    s=list(input())
    s.sort()
    S=''.join(s)
    if S not in dic:
        dic[S]=1
    else:
        dic[S]+=1
for v in dic.values():
    if v>=2:
        ans+=v*(v-1)//2
print(ans)
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp1 = [0] * (n + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp[i] = max(feat)
    for i in range(5001, n+1):
        dp1[i] = max(i, dp1[i-ga]+gb, dp1[i-sa]+sb, dp1[i-ba]+bb)
else:
    for i in range(1, n+1):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp1[i] = max(feat)

B = dp1[-1]
dp2 = [0] * (B + 1)
if B > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

    for i in range(5001, B+5001):
        dp2[i] = max(i-5000, dp2[i-gb]+ga, dp2[i-sb]+sa, dp2[i-bb]+ba)
else:
    for i in range(1, B+1):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

print(dp2[-1])


### FIXED CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp1 = [0] * (n + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp[i] = max(feat)
    for i in range(5001, n+1):
        dp1[i] = max(i, dp1[i-ga]+gb, dp1[i-sa]+sb, dp1[i-ba]+bb)
else:
    for i in range(1, n+1):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp1[i] = max(feat)

B = dp1[-1]
dp2 = [0] * (B + 1)
if B > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

    for i in range(5001, B+1):
        dp2[i] = max(i, dp2[i-gb]+ga, dp2[i-sb]+sa, dp2[i-bb]+ba)
else:
    for i in range(1, B+1):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

print(dp2[-1])
import sys
input = sys.stdin.readline

import sympy

N = int(input())

total = 0
for i in range(1,N):
    total += len(sympy.divisors(i))

print(total)


### FIXED CODE ###

import sys
import math

input = sys.stdin.readline

N = int(input())

total = 0
for i in range(1, N):
    total += (N-1) // i

print(total)
N,W = map(int, input().split())
dp = [0]*(W+1)

for i in range(1,N+1):
    v,w = map(int,input().split())
    for j in range(w-1, W, -1):
    	print(j)
        x = v+dp[j-w]
        if x > dp[j]: dp[j] = x

print(dp[W])



### FIXED CODE ###

N , W = map(int,input().split())
dp = [0]*(W+1)

for i in range(N):
    n , m = map(int,input().split())
    for j in range(W,m-1,-1):
        x = n + dp[j-m]
        if x >= dp[j]:
            dp[j] = x
            
print(dp[W])
N, K = map(int,input().split())
if N % 2 != 0:
    if (N/2 + 1) >= K:
    print("YES")
    else:
    print("NO")
else:
    if (N/2) >= K:
    print("YES")
    else:
    print("NO")


### FIXED CODE ###

N, K = map(int,input().split())
if N % 2 != 0:
    if (N/2 + 1) >= K:
        print("YES")
    else:
        print("NO")
else:
    if (N/2) >= K:
        print("YES")
    else:
        print("NO")
=int(input())
count=1
ans=10000000000000
k=c
for i in range(1,int(c**(1/2)+100000)):
    if c%i==0:
        count*=i
        k=int(k/i)
        if ans>count+k:
            ans=count+k
            count=0
            k=c
        else:
            count=0
            k=c
print(ans-2)


### FIXED CODE ###

c=int(input())
count=1
ans=10000000000000
k=c
for i in range(1,int(c**(1/2)+100000)):
    if c%i==0:
        if ans>i+int(c/i):
            ans=i+int(c/i)
        else:
            continue
print(ans-2)
a = int(input())
b = int(input())
c = int(input())
x = int(input())
 
result = 0             //initialized to zero
 
for ai in range(a+1):
    for bi in range(b+1):
        for ci in range(c+1):
            amount = 500 * ai + 100 * bi + 50 * ci        //formula
            if amount == x:
                result += 1
 
print(result)        //output

### FIXED CODE ###

coinA = int(input())
coinB = int(input())
coinC = int(input())
want = int(input())
ways = 0
i = 0
while i <= coinA:
    j = 0
    while j <= coinB:
        k = 0
        while k <= coinC:
            if i*500 + j*100 + k*50 == want:
                ways = ways + 1
            k = k + 1
        j = j + 1
    i = i + 1
print(ways)
s = input()

if not s.count("a") == 1:
  print("NO")
  break
elif not s.count("b") == 1:
  print("NO")
  break
elif not s.count("c") == 1:
  print("NO")
  break
else:
  print("YES")

### FIXED CODE ###

s = input()
 
if not s.count("a") == 1:
  print("No")
elif not s.count("b") == 1:
  print("No")
elif not s.count("c") == 1:
  print("No")
else:
  print("Yes")
import collections
 
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  for j in range(20):
    if(2**j>i):
      k=2**j-i
      break
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)

### FIXED CODE ###

import collections
import math
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
c=collections.Counter(a)
ans=0
for i in a:
  j=int(math.log2(i))+1
  k=2**j-i
  if k in c.keys():
    if i==k and c[i]>1:
      c[i]-=2
      ans+=1
    elif i!=k and c[i]>0 and c[k]>0:
      c[i]-=1
      c[k]-=1
      ans+=1
print(ans)
import collections
N,K=map(int,input().split())
a=list(map(int,input().split()))
table=collections.defaultdict(int)
for i in range(N):
  table[a[i]]+=1
table= list(table.items())
if len(table)<=K:
  print(0)
else:
  ans=0
  table.sort(key =lambda x:x[1])
  for i in range(N-K):
    ans+=table[i][1]
  print(ans)

### FIXED CODE ###

import collections
N,K=map(int,input().split())
a=list(map(int,input().split()))
table=collections.defaultdict(int)
for i in range(N):
  table[a[i]]+=1
table= list(table.items())
if len(table)<=K:
  print(0)
else:
  ans=0
  table.sort(key =lambda x:x[1])
  for i in range(len(table)-K):
    ans+=table[i][1]
  print(ans)
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    graph = [[] for _ in range(N)]
    for i in range(M):
        graph[x[i]-1].append(y[i]-1)

    memo = {}

    def dfs(v):
        if v in memo:
            return memo[v]

        if graph[v]:
            res = max(dfs(child) for child in graph[v])
            memo[v] = res + 1
        else:
            res = 0
            memo[v] = 0

        return memo[v]

    print(max(dfs(i) for i in range(N)))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)


def dfs(v, graph, memo):
    if v in memo:
        return memo[v]

    if graph[v]:
        res = float("-inf")
        for child in graph[v]:
            res = max(res, dfs(child, graph, memo) + 1)
        memo[v] = res
    else:
        res = 0
        memo[v] = 0

    return memo[v]


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    graph = [[] for _ in range(N)]
    for i in range(M):
        graph[x[i]-1].append(y[i]-1)

    memo = {}

    res = float("-inf")
    for i in range(N):
        res = max(res, dfs(i, graph, memo))
    print(res)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (M)  # type: "List[int]"
    y = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()
from fractions import gcd
n,m=map(int,input().split())
s = input()
t = input()
g = gcd(n,m)
ng = n//g
mg = m//g
for i in range(g):
    if s[ng*i]!=t[mg*i]):
        print("-1")
        break
else:
    print(n*m//g)

### FIXED CODE ###

from fractions import gcd
n,m=map(int,input().split())
s = input()
t = input()
g = gcd(n,m)
ng = n//g
mg = m//g
for i in range(g):
    if s[ng*i]!=t[mg*i]:
        print("-1")
        break
else:
    print(n*m//g)
n,x=map(int,input().split())
L = list(map(int,input().split()))
count=1
D=0
for i in range(n):
    if D>x:
        print(count)
        break
    else:
        D=D+L[i]     
        count+=1

### FIXED CODE ###

n,a=map(int,input().split())
if n>=a:
    print(10)
else:
    print(0)
a,b = input().split()
if a>b:
  print('>')
else if a<b:
  print('<')
else if a==b:
  print('=')

### FIXED CODE ###

a,b = input().split()
if a>b:
  print('>')
elif a<b:
  print('<')
elif a==b:
  print('=')