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

def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        while j<w:
            flag=0
            for p in range(h):
                ll[l[p]]+=S[p][j]
                if ll[l[p]]>k:
                    flag=1
            if flag:
                ans_+=1
                ll=[0]*h
            else:
                j+=1
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        flag=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k and flag==0:
                flag=1
                ans_+=1
                ll=[0]*h
            elif max(ll)>k and flag==1:
                ans_=10**5
                break
            else:
                j+=1
                flag=0
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    while data[a]!=a:
        a=data[a]
    while data[b]!=b:
        b=data[b]
    if a!=b:
        data[a]=b
        cnt-=1
print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
def find(x):
    if data[x]==x:
        return x
    else:
        data[x]=find(data[x])
        return data[x]
for i in range(m):
    a,b=map(int,input().split())
    a=find(a-1)
    b=find(b-1)
    if a!=b:
        data[a]=b
        cnt-=1
print(cnt)
### BUGGY CODE ###

h, n = map(int, input().split())
dp = [0] * (h+1)
for i in range(n):
        a, b = map(int, input().split())
        for j in range(1, h+1):
            if i == 0 and j - a <= 0:
                dp[j] = b
            elif i == 0:
                dp[j] = dp[j-a] + b
            elif j - a <= 0:
                dp[j] = min(dp[j], b)
            else:
                dp[j] = min(dp[j], dp[j-a] + b)
print(dp[-1])

### FIXED CODE ###

h, n = map(int, input().split())
dp = [0] * (h+1)
for i in range(n):
        a, b = map(int, input().split())
        for j in range(1, h+1):
            if i == 0 and j - a <= 0:
                dp[j] = b
            elif i == 0:
                dp[j] = dp[j-a] + b
            elif j - a <= 0:
                dp[j] = min(dp[j], b)
            else:
                dp[j] = min(dp[j], dp[j-a] + b)
print(dp[-1])
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:   
    for j in range(1,K+1):
        dp[j]= abs(h[0]-h[j])
    
    for i in range(K,N):
        
        
        dp[i]= min(dp[i-k]+abs(h[i-k]-h[i]) for k in range(1,K+1))
        
        #dp[i]=np.min(list1)
         
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
dp[1]=abs(h[1]-h[0])
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:  
    for i in range(2,N):
      j=max(0,i-K)
      dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
      #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

# 入力
N = int(input())
A = list(map(int,input().split()))

ans = 0
P = 10**9+7
bit = [0]*60

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(60):
    if bit[i] != 0 and bit[i] != N:
        ans += bit[i]*(N-bit[i])*(2**i)
        ans %= P

print(ans)


### FIXED CODE ###

# 入力
N = int(input())
A = list(map(int,input().split()))

ans = 0
P = 10**9+7
bit = [0 for i in range(70)]

# 各bit独立に1が何個あるか数える
for i in range(N):
    S = bin(A[i])
    for j in range(1,len(S)-1):
        if S[-1*j] == '1':
            bit[j-1] += 1

# 各bitの1の個数と0の個数の積が、XOR和が1になる数字の個数と一致
for i in range(70):
    ans += (2**i)*bit[i]*(N-bit[i])
    ans %= P

print(ans)
### BUGGY CODE ###

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

prev = 0
point = 1
for i in range(N):
    if i < K:
        point *= A[i]
    else:
        prev = point
        point *= A[i]
        point /= A[i-K]
        if prev < point:
            print("Yes")
        else:
            print("No")
    


### FIXED CODE ###

from sys import stdin
readline = stdin.readline

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

prev = 0
point = 1
ans = []
for i in range(N):
    if i >= K:
        if A[i-K] < A[i]:
            ans.append("Yes")
        else:
            ans.append("No")
print(*ans, sep='\n')
### BUGGY CODE ###

import numpy as np
n = int(input())
a = tuple(map(int, input().split()))
b = np.full(n, np.inf)
for i in range(n-1):
    x = abs(sum(a[:i+1])-sum(a[i+1:]))
    b[i] = x
print(int(min(b)))


### FIXED CODE ###

import numpy as np
n = int(input())
a = tuple(map(int, input().split()))
b = np.full(n, np.inf)
f = 0
s = sum(a)
for i in range(n-1):
    f += a[i]
    s -= a[i]
    x = abs(f - s)
    b[i] = x
print(int(min(b)))
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.buffer.readline
    s=b' '+input()[:-1]
    t=b' '+input()[:-1]
    n,m=len(s),len(t)
    dp=[[0]*m for _ in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if s[i]==t[j]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    ans=[]
    i,j=n-1,m-1
    while dp[i][j]:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        else:
            ans.append(s[i])
            i-=1
            j-=1
    print(''.join(map(chr,ans))[::-1])
main()

### FIXED CODE ###

s=' '+input()
t=' '+input()
dp=[[0]*len(t)for _ in range(len(s))]
for i in range(1,len(s)):
    for j in range(1,len(t)):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ans=[]
i,j=len(s)-1,len(t)-1
while dp[i][j]:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i])
        i-=1
        j-=1
print(''.join(ans[::-1]))
### BUGGY CODE ###

from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a)|1 and (SA:=SA+a)|1 and (SB:=SB+b)|1 and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


### FIXED CODE ###

from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)
### BUGGY CODE ###

k=int(input())

p=0
for i in range(k+2) :
    p+=7*(10**i)
    if p%k==0 :
        print(i+1)
        exit()
else :
    print(-1)

### FIXED CODE ###

k=int(input())
q=[7]
Q=[0]

for i in range(k) :
    q.append((q[i]*10)%k)
    if (q[i]+Q[i])%k==0 :
        print(i+1)
        exit()
    Q.append((q[i]+Q[i])%k)
    
else :
    print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*(n)
m=1
for i in range(n):
    dp[i]=m*l[i]
    m*=l[i]
x=dp[k-1]
for i in range(k,n):
    cur=dp[i]//(dp[i-k])
    
    if cur>x:
        print("Yes")
    else:
        print("No")
    x=cur
    


### FIXED CODE ###

n,k = map(int,input().split())
a=list(map(int,input().split()))
 
for i in range(k,n):
    if(a[i] > a[i-k]):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from queue import *
N, M = map(int, input().split())
N *= 3
es = [[] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : (int(x)-1)*3, input().split())
    es[u].append(v+1)
    es[u+1].append((v+2))
    es[u+2].append((v))
S, T = map(lambda x : (int(x)-1)*3, input().split())
dist = [-1 for i in range(N)]
dist[S] = 0
q = Queue()
q.put(S)
while not q.empty():
    v = q.get()
    for u in es[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + 1
            q.put(u)
if dist[T] != -1:
    print(dist[T] // 3)
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

from queue import *
N, M = map(int, input().split())
N *= 3
es = [[] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : (int(x)-1)*3, input().split())
    es[u].append(v+1)
    es[u+1].append((v+2))
    es[u+2].append((v))
S, T = map(lambda x : (int(x)-1)*3, input().split())
dist = [-1 for i in range(N)]
dist[S] = 0
q = Queue()
q.put(S)
while not q.empty():
    v = q.get()
    for u in es[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + 1
            q.put(u)
if dist[T] != -1:
    print(dist[T] // 3)
else:
    print(-1)
### BUGGY CODE ###

R, G, B, N =list(map(int, input().split()))
# R = 13
# G = 1
# B = 4
# N = 3000
X, Y, Z = sorted([R, G, B], reverse=True)
cnt = 0
for i in range(N//X+1):
    for j in range(N+1):
        if (X*i+Y*j>N): break
        cnt += ((N-X*i-Y*j)%Z == 0)
print(cnt)


### FIXED CODE ###

R, G, B, N =list(map(int, input().split()))
# R = 13
# G = 1
# B = 4
# N = 3000
X, Y, Z = sorted([R, G, B], reverse=True)
cnt = 0
for i in range(N//X+1):
    for j in range(N+1):
        tmp = X*i+Y*j 
        if (tmp>N): break
        cnt += ((N-tmp)%Z == 0)
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# import math

def conbination(n, r):
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    if r == 0:
        return 1
    bunshi = 1
    for i in range(n, n-r, -1):
        bunshi *= i
    bunbo = 1
    for i in range(r, 0, -1):
        bunbo *= i
    return bunshi // bunbo

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

if N == K:
    print(1)
    for i in range(2, K+1):
        print(0)
else:
    for i in range(1, K+1):
        c_blue = conbination(K-1, i-1)
        c_red = conbination(N-K+1, i)
        print((c_blue * c_red) % (10**9 + 7))


### FIXED CODE ###

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

def conbination(n, r):
    return f[n] // (f[r] * f[n-r])

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

f = [1]
for i in range(1, N+1):
    f.append(int(f[i-1]*i))

for i in range(1, K+1):
    if i > N-K+1:
        print(0)
        continue
    c_blue = conbination(K-1, i-1)
    c_red = conbination(N-K+1, i)
    print((c_blue * c_red) % (10**9 + 7))
### BUGGY CODE ###

import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    cos_per.append([d+1,sum(tmp)/p])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-1個はコスパが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
#choice = set(range(1,D+1))
#choiceList = []
#for i in range(min_num-1):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
#-足し上げる-#
choice = set(range(1,D+1))
ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    tmp = []
    for ci in ch:
        tmp+=score[ci-1]
    times = 0
    total = 0
    for sc in tmp:
        total += sc
        times += 1
        if total >= G:
            ans = min(ans,times)
            break
print(ans)     


### FIXED CODE ###

import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
maxS = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    maxS.append([p,sum(tmp)])
    #cos_per.append([d+1,sum(tmp)/p])
    cos_per.append([d+1,d+1])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-2個はスコアが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
choice = set(range(1,D+1))
#choiceList = []
#for i in range(0,min_num-3):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
 
#-足し上げる-#

ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    times = 0
    total = 0
    flag = 0
    for ci in ch:
        if total + maxS[ci-1][1] <G:
            total += maxS[ci-1][1]
            times += maxS[ci-1][0]
        else:
            for sc in score[ci-1]:
                total += sc
                times += 1
                if total >= G:
                    ans = min(ans,times)
                    falg = 1
                    break
    if flag ==1:
        break
print(ans)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A.sort()
Balls = {k: len(list(g)) for k, g in itertools.groupby(A)}
cnt = 0
while len(Balls.keys()) > K:
    change = -1
    for k, v in Balls.items():
        if v == min(Balls.values()):
            cnt += v
            change = k
            break
    del Balls[change]
print(cnt)

### FIXED CODE ###

import itertools
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A.sort()
Balls = [len(list(g)) for k, g in itertools.groupby(A)]
Balls.sort(reverse=True)
cnt = 0
while len(Balls) > K:
    cnt += Balls.pop()
print(cnt)
### BUGGY CODE ###

from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if C[a] == 1:
            ans += 1
        else:
            dp[a] = True
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)
### BUGGY CODE ###

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

key = [0]*N
x = [list(map(int,input().split())) for i in range(M)]

for i in range(M):
	for j in range(x[i][0],x[i][1]+1):
		key[j-1] += 1

count = 0
for k in range(N):
	if key[k] == M:
		count += 1

print(count)

### FIXED CODE ###

N,M = map(int,input().split())
X = [list(map(int,input().split())) for i in range(M)]

keymax = 10**6
keymin = 0
for i in range(M):
	if X[i][0] > keymin:
		keymin = X[i][0]
	if X[i][1] < keymax:
		keymax = X[i][1]

if keymax >= keymin:
	print(keymax-keymin+1)
else:
	print("0")
### BUGGY CODE ###

s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]].append(i)
repeat = 0
cur_index = -1
for c in t:
  indices = dictionary[c]
  if not indices:
    repeat = 0
    cur_index = -2
    break
  next_index = indices[0]
  for index in indices:
    if index > cur_index:
      next_index = index
      break
  else:
    repeat += 1
  cur_index = next_index
print(len_s * repeat + cur_index + 1)

### FIXED CODE ###

s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [[], 0] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]][0].append(i)
  dictionary[s[i]][1] += 1
repeat = 0
cur_index = -1
for c in t:
  indices, len_indices = dictionary[c]
  if len_indices == 0:
    repeat = 0
    cur_index = -2
    break
  inf = -1
  sup = len_indices
  while sup - inf > 1:
    x = (inf + sup) // 2
    if indices[x] > cur_index:
      sup = x
    else:
      inf = x
  if sup == len_indices:
    repeat += 1
    cur_index = indices[0]
  else:
    cur_index = indices[sup]
print(len_s * repeat + cur_index + 1)
### BUGGY CODE ###

def main():
	n, *a = map(int, open(0).read().split())
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for l in range(n)[::-1]:
		for r in range(n - l)[::-1]:
			dp[l][r] = max(a[l] - dp[l + 1][r], a[n - 1 - r] - dp[l][r + 1])
	print(dp[0][0])

if __name__ == '__main__':
	main()

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1) for _ in range(n+1)]
for l in range(n)[::-1]:
	for r in range(n)[::-1]:
		if l+r<=n-1:
			dp[l][r]=max(a[l]-dp[l+1][r],a[n-1-r]-dp[l][r+1])
print(dp[0][0])
### BUGGY CODE ###

#ABC130-E Common Subsequence
"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7

#dp table
dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(m+2) for _ in range(n+2)]
dp0[0][0] = 1
#process1
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] += dp0[i][j]
        dp1[i][j] += dp0[i][j]
        dp1[i][j+1] += dp1[i][j]
        if s[i] == t[j]:
            dp0[i+1][j+1] += dp1[i][j]


print(dp1[n][m]%mod)


### FIXED CODE ###

#ABC130-E Common Subsequence
"""
問題：
整数列のリストが与えられる
空であるものも含めて、sとtの部分列として等しいものの個数を求めよ
解法：
LCSのmaxではなくsumのバージョンでかつ、
数え上げなので重複をなくさなければならない。
具体的には、
dp[i][j]:sをi文字目迄見た時のtをj文字目迄見た時に、
dp0:横方向(j方向)を優先して遷移した後に、縦方向(i方向)への遷移を行った時の合計
dp1:縦方向、横方向への遷移を行った時の合計
として、dp1[-1][-1]が答え。

"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m = map(int,readline().split())
s = list(map(int,readline().split())) + [-1]
t = list(map(int,readline().split())) + [-2]
mod = 10**9+7

#dp table
dp0 = [[0]*(m+2) for _ in range(n+2)]
dp1 = [[0]*(m+2) for _ in range(n+2)]
dp0[0][0] = 1
#process1
for i in range(n+1):
    for j in range(m+1):
        dp0[i+1][j] += dp0[i][j]%mod
        dp1[i][j] += dp0[i][j]%mod
        dp1[i][j+1] += dp1[i][j]%mod
        if s[i] == t[j]:
            dp0[i+1][j+1] += dp1[i][j]%mod


print(dp1[n][m]%mod)
### BUGGY CODE ###

n = int(input())

nums = list(map(int, input().split()))
q = int(input())

ans = []

for _ in range(q):
    b, c = map(int, input().split())
    
    nums = sorted(nums)

    if b in nums:
        cnt = 0
        is_b = True
        while is_b:
            nums.remove(b)
            cnt += 1
            if not b in nums:
                is_b = False
                nums = nums + [c] * cnt


    ans.append(sum(nums))

for a in ans:
    print(a)

### FIXED CODE ###

from collections import Counter

n = int(input())

nums = tuple(map(int, input().split()))

count = Counter(nums)
s = sum(nums)

answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + (c - b) * count[b]
    count[c] += count[b]
    count[b] = 0
    answers.append(s)
    
for answer in answers:
    print(answer)
### BUGGY CODE ###

#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

A, B, N = [int(_) for _ in input().split()]

def floor(t):
    return t // 1

ma = 0
x = 0
while True:
    if x > N: break
    a = floor(A*x/B) - A * floor(x/B)
    x += 1
    if a > ma:
        ma = a

print(int(ma))   

### FIXED CODE ###

#! /usr/bin/env python3

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

A, B, N = [int(_) for _ in input().split()]

x = min(B-1, N) # 0 <= x < B and 0 <= x <= N
a = (A * x) // B - A * (x // B)

print(int(a))
### BUGGY CODE ###

n = 50001
is_prime = [True for i in range(n)]
is_prime[0] = is_prime[1] = False
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = False
        j += i
    i += 1

cnt_pair = [0 for i in range(n)]
for i in range(n):
    cnt = 0
    if i%2 == 0:
        for j in range(n):
            if is_prime[j] and is_prime[n - j]:
                cnt += 1
        cnt_pair[i] = cnt

while True:
    n = int(input())
    if n == 0:
        break
    print(cnt_pair[n])



### FIXED CODE ###

n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

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

if len(set(num_lists)) <= k:
  ans = 0
else:
  num_counts = {}
  for i in set(num_lists):
    num_counts[i] = num_lists.count(i)
  
  numbers = list(num_counts.values())
  numbers.sort()
  ans = 0
  for i in range(len(set(num_lists))-k):
    ans += numbers[i]
print(ans)


### FIXED CODE ###

from collections import Counter

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

num_counts = dict()
length = len(set(num_lists))
ans = 0

if length > k:
  d = Counter()
  d.update(num_lists)
  count_sorted = list(d.values())
  count_sorted.sort()
  for i in range(length - k):
    ans += count_sorted[i]

print(ans)