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

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

#縦k、横kのマスに移動させて考える
n, k = map(int, input().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = input().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
for i in range(lx):
    for j in range(x[i], k):
        graph[j][y[i]] += 1
    for j in range(x[i]):
        graph[j][0] += 1
        graph[j][y[i]] -= 1

lmx = len(mx)
for i in range(lmx):
    for j in range(mx[i], k):
        graph[j][my[i]] -= 1
    for j in range(mx[i]):
        graph[j][0] -= 1
        graph[j][my[i]] += 1

for i in range(k):
    for j in range(k-1):
        graph[i][j+1] += graph[i][j]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)

### FIXED CODE ###

import sys

#縦k、横kのマスに移動させて考える
n, k = map(int, sys.stdin.readline().strip().split())
x = []
y = []
mx = []
my = []
for _ in range(n):
    xx, yy, c = sys.stdin.readline().strip().split()
    xx = int(xx)
    yy = int(yy)
    if c == 'W':
        xx += k
    xx %= 2 * k
    yy %= 2 * k
    if xx >= k:
        if yy >= k:
            x.append(xx - k)
            y.append(yy - k)
        else:
            mx.append(xx - k)
            my.append(yy)
    else:
        if yy >= k:
            mx.append(xx)
            my.append(yy - k)
        else:
            x.append(xx)
            y.append(yy)

graph = [[0 for _ in range(k)] for __ in range(k)]

#累積和
#lx + lmx = n
lx = len(x)
graph[0][0] += lx
for i in range(lx):
    graph[x[i]][0] -= 1
    graph[0][y[i]] -= 1
    graph[x[i]][y[i]] += 2

lmx = len(mx)
graph[0][0] -= lmx
for i in range(lmx):
    graph[mx[i]][0] += 1
    graph[0][my[i]] += 1
    graph[mx[i]][my[i]] -= 2

for i in graph:
    for j in range(k-1):
        i[j+1] += i[j]

for i in range(k):
    for j in range(k-1):
        graph[j+1][i] += graph[j][i]

#最大値、最小値を取得
big = max([max(i) for i in graph]) + lmx
small = min([min(i) for i in graph]) - lx

if big + small >= 0:
    print(big)
else:
    print(-small)
### BUGGY CODE ###

import math
def isprime(n):
    if n==1 or n==0:
        return False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0 and n!=i:
            return False
    return True


Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
for i in range(Q):
    l[i], r[i] = map(int, input().split())
X=max(r)
P=[0 for i in range(X+1)]
for i in range(X+1):
    if isprime(i) and i%2==1:
        if isprime((i+1)//2):
            P[i]+=1
S=[sum(P[:i+1]) for i in range(X+1)]
for i in range(Q):
    print(S[r[i]]-S[l[i]-1])


### FIXED CODE ###

import math
Q=int(input())
l=[0 for i in range(Q)]
r=[0 for i in range(Q)]
M=0
for i in range(Q):
    l[i],r[i]=map(int,input().split())
    if M<r[i]:
        M=r[i]
P=[True for i in range(M+1)]
P[0]=False
P[1]=False
S=[False for i in range(M+1)]
for i in range(2,int(math.sqrt(M))+1):
    if P[i]:
        for j in range(i*2,M+1,i):
            P[j]=False
R=[0 for i in range(M+1)]
k=0
for i in range(M+1):
    if P[i] and i%2==1:
        if P[(i+1)//2]:
            S[i]=True
            k+=1
    R[i]=k
for i in range(Q):
    print(R[r[i]]-R[l[i]-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
x = []
pre = s.index(t[0])
x.append(pre+1)
ss = s
for i in range(1,m):
    ss = ss[pre+1:] + ss[:pre+1]
    inde = ss.index(t[i])
    x.append(inde+1)
    pre = inde
print(sum(x))


### FIXED CODE ###

#!/usr/bin/env python3
#ABC138 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
f = [False]*26
f2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(n):
    f[alpha.index(s[i])] = True
for i in range(m):
    f2[alpha.index(t[i])] = True
for i in range(26):
    if not f[i] and f2[i]:
        print(-1)
        quit()
ans = 0
pre = s.index(t[0])
ans += pre+1
for i in range(1,m):
    s = s[pre+1:] + s[:pre+1]
    inde = s.index(t[i])
    ans += inde+1
    pre = inde
print(ans)
### BUGGY CODE ###

s = input()
res = 0
while True:
    a = s.find('01')
    b = s.find('10')
    if a != -1 or b != -1:

        if a != -1:
            if b != -1:
                if a < b:
                    s = s[:a] + s[a + 2:]
                    res += 2
                else:
                    s = s[:b] + s[b + 2:]
                    res += 2
            else:
                s = s[:a] + s[a + 2:]
                res += 2
        else:
            s = s[:b] + s[b + 2:]
            res += 2
    else: break

print(res)

### FIXED CODE ###

s = input()
a = s.count('0')
b = s.count('1')
if a > b:
    print(b * 2)
elif a < b:
    print(a * 2)
elif a==b and a!=0 and b!= 0:
    print(a * 2)
else:
    print(0)
### BUGGY CODE ###

def main():
    import numpy as np
    n,t=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(n)]

    dp1=np.zeros([n+1,t],dtype=np.int64)
    dp2=np.zeros([n+1,t],dtype=np.int64)
    for i in range(n):
        a1=F[i][0]
        b1=F[i][1]
        a2=F[n-i-1][0]
        b2=F[n-i-1][1]
        dp1[i+1][:a1]=dp1[i][:a1]
        dp1[i+1][a1:]=np.maximum(dp1[i][a1:],dp1[i][:-a1]+b1)
        dp2[i+1][:a2]=dp2[i][:a2]
        dp2[i+1][a2:]=np.maximum(dp2[i][a2:],dp2[i][:-a2]+b2)

    
    ans=0
    for i in range(n):
        b=F[i][1]
        for j in range(t):
            ans=max(dp1[i][j]+dp2[n-i-1][t-1-j]+b,ans)
    print(ans)          
  
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    n,t=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(n)]

    dp1=[[0]*t for _ in range(1+n)]
    dp2=[[0]*t for _ in range(1+n)]
    for i in range(n):
        a1=F[i][0]
        b1=F[i][1]
        a2=F[n-i-1][0]
        b2=F[n-i-1][1]
        for j in range(t):
            if j<a1:
                dp1[i+1][j]=dp1[i][j]
            else:
                dp1[i+1][j]=max(dp1[i][j],dp1[i][j-a1]+b1)
            
            if j<a2:
                dp2[i+1][j]=dp2[i][j]
            else:
                dp2[i+1][j]=max(dp2[i][j],dp2[i][j-a2]+b2)
    
    ans=0
    for i in range(n):
        b=F[i][1]
        for j in range(t):
            ans=max(dp1[i][j]+dp2[n-i-1][t-1-j]+b,ans)
    print(ans)          
  
if __name__=='__main__':
    main()
### BUGGY CODE ###

N,K = map(int,input().split())
XY = []

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


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
XY = []

for i in range(N):
    x,y = map(int,input().split())
    XY.append((x,y))


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 0
ans1 = [0] * n
for i in range(1,n):
  for j in range(1,n):
    for k in range(1,n):
      ans = i**2 + j**2 +k**2 + i*j + j*k + k*i
      for l in range(n-1):
        if(l+1 == ans):
          ans1[l] += 1
for i in range(n):
  print(ans1[i])

### FIXED CODE ###

n = int(input())

ans = 0
ans1 = [0] * 10050
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      ans = i**2 + j**2 +k**2 + i*j + j*k + k*i
      if(ans < 10050):
        ans1[ans] += 1
for i in range(n):
  print(ans1[i+1])
### BUGGY CODE ###

def chk(A,B):
  nL=len(A)
  if A[0]==B[0]:
    if nL==1:
      return 1
    else:
      return chk(A[1:],B[1:])
  else:
    return 0
n=int(input())
s=[sorted(input()) for i in range(n)]
s.sort()
cnt=0
for i in range(n-1):
  for j in range(i+1,n):
    cnt+=chk(s[i],s[j])
print(cnt)

### FIXED CODE ###

n=int(input())
A={}
for i in range(n):
  s=str(sorted(input()))
  if s in A.keys():
    A[s]+=1
  else:
    A[s]=1
ans=0
for i in list(A.values()):
  ans+=int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

import numpy as np
N, A = map(int, input().split())
x = list(map(int, input().split()))

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

ans = 0
for k in range(1, N+1):
    ans += check(N, k, k * A)
    # ans += dp[N][k][k * A]

print (ans)

### FIXED CODE ###

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

X = max(x)
if X < A:
    X = A

def check(j, k, s):
    if dp[j][k][s] != -1:
        return dp[j][k][s]
    if j == 0 and k == 0 and s == 0:
        dp[j][k][s] = 1
        return 1
    if j >= 1 and s < x[j-1]:
        a = check(j-1, k ,s)
        dp[j][k][s] = a
        return a
    if j >= 1 and k >= 1 and s >= x[j-1]:
        a = check(j-1, k, s) + check(j-1, k-1, s-x[j-1])
        dp[j][k][s] = a
        return a
    dp[j][k][s] = 0
    return 0
        
dp = [[[-1] * (N*X+1) for _ in range(N+1)] for _ in range(N + 1)]
# dp = np.array(dp)
# print (dp)
# for j in range(N+1):
#     for k in range(N+1):
#         for s in range(N*X + 1):
#             print (j, k, s)
#             dp[j][k][s] = check(j, k, s)

ans = 0
for k in range(1, N+1):
    ans += check(N, k, k * A)
    # ans += dp[N][k][k * A]

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
px = [(1 + p[i])/2 for i in range(n)]

ans = 0

for i in range(0, n - k + 1):
    ans = max(ans, sum(px[i: i + k]))
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
px = [(1 + p[i])/2 for i in range(n)]

ans = sum(px[0: 0 + k])
bef = sum(px[0: 0 + k])
for i in range(1, n - k + 1):
    bef = bef-px[i-1]+px[i+k-1]
    ans = max(ans, bef)
print(ans)
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

candidate_dict = {}
candidate_dict[len(n_dm_set)] = d_dm

bucket = [0]*(N+1)
for t in n_dm_set:
    bucket[t] = -1

d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    t = t_arr[i]
    if bucket[t] != 0:
        continue
    d = d_arr[i]
    bucket[t] = d
    if len(small_arr) == 0:
        break
    d_x += d
    d_x -= small_arr[-1]
    small_arr = small_arr[:-1]
    nt_x += 1
    candidate_dict[nt_x] = d_x

ans = 0
for k,v in candidate_dict.items():
    ans = max(ans, k*k+v)

print(ans)


### FIXED CODE ###

N,K = (int(x) for x in input().split())
t_arr = [0]*(N+1)
d_arr = [0]*(N+1)
for i in range(N):
    t,d = tuple(int(x) for x in input().split())
    t_arr[i+1] = t
    d_arr[i+1] = d

td_index = list(range(1,N+1))
td_index.sort(key=lambda x:d_arr[x], reverse=True)

n_dm_set = set()
small_arr = []
d_dm = 0
for i in td_index[:K]:
    t = t_arr[i]
    d = d_arr[i]
    if t in n_dm_set:
        small_arr.append(d)
    n_dm_set.add(t)
    d_dm += d

current_max = len(n_dm_set)**2+d_dm

n_x_set = set(n_dm_set)
d_x = d_dm
nt_x = len(n_dm_set)
for i in td_index[K:]:
    if not small_arr:
        break
    t = t_arr[i]
    d = d_arr[i]
    if t in n_x_set:
        continue
    n_x_set.add(t)
    d_x += d
    d_x -= small_arr.pop()
    nt_x += 1
    current_max = max(current_max, nt_x**2+d_x)

print(current_max)
### BUGGY CODE ###

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

A=[[0]*2 for i in range(N)]
Ans=[0]*(N+1)
P=[[0]*2 for i in range(Q)]
X=[0]*Q

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())

for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())

A.sort()
P.sort()

for i in range(Q):
    Ans[P[i][0]]+=P[i][1]

for i in range(N):
    Ans[A[i][1]]+=Ans[A[i][0]]

for i in range(1,N+1):
    print(Ans[i],end=" ")


### FIXED CODE ###

import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=0
for j in range(len(bin(max(a)))-2):
    cnt1=0
    cnt0=0
    for i in range(n):
      if (a[i]>>j)&1:
        cnt1+=1
      else:
        cnt0+=1
    s+=(cnt1*cnt0*2**j)%(10**9+7)
print(s%(10**9+7))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
for j in range(60):
    cnt1=sum([1 for i in a if i>>j&1])
    cnt0=n-cnt1
    ans+=(cnt1*cnt0*2**j)
print(ans%(10**9+7))
### BUGGY CODE ###

import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


n, k = invr()
res = Decimal(0)
for i in range(1, n+1):
    if i >= (k-1):
        res += Decimal(1/n)
    else:
        x = int(ceil(log2((k)/i)))
        res += Decimal((1/n) * (1/2)**x)
print(res)


### FIXED CODE ###

import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


n, k = invr()
res = 0
for i in range(1, n+1):
    if i > (k-1):
        res += 1/n
    else:
        x = ceil(log2((k)/i))
        res += (1/n) * (1/2)**x
print(res)
### BUGGY CODE ###

N,M = map(int,input().split())
ans = ('IMPOSSIBLE')
f1tob = []
fbtoN = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        f1tob.append(b)
    elif b == N:
        fbtoN.append(a)
for j in f1tob:
    if j in fbtoN:
        ans = 'POSSIBLE'
        break
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
ans = ('IMPOSSIBLE')
f1tob = []
fbtoN = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        f1tob.append(b)
    elif b == N:
        fbtoN.append(a)
f1toba = set(f1tob)
fbtoNa = set(fbtoN)
if bool(fbtoNa & f1toba):
    ans = 'POSSIBLE'
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      for k in range(13):
        DP[i+1][k]+=DP[i][R[r][j][k]]
  else:
    for k in range(13):
      DP[i+1][k]+=DP[i][R[r][int(s[i])][k]]
print(DP[n][5]%(10**9+7))

### FIXED CODE ###

mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a

if ans > (10 ** 18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
dekai = False
for a in A:
    ans *= a
    if ans > (10 ** 18):
        dekai = True
        break

if 0 in A:
    print(0)
elif dekai:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
import os
import math
import itertools
def factorize(n):
    b = 2
    fct = []
    fct.append(1)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

N = int(input())
listN = factorize(N)
x = 0
y = 0
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(1,len(listN)):
        tmp = list(itertools.combinations(listN,i))
        tmp = list(set(tmp))
        for j in range(len(tmp)):
            x0,y0 = 1,1
            for k in range(len(tmp[j])):
                x0 *= tmp[j][k]
                y0 = N//x0
                if mini > abs(x0+y0):
                    mini = abs(x0+y0)
                    x = x0
                    y = y0
print(x-1+y-1)


### FIXED CODE ###

import sys
import os

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
listN = make_divisors(N)
mini = 10**12
if len(listN) == 1:
    x = N
    y = 1
else:
    for i in range(len(listN)):
        x = listN[i]
        y = N//x
        mini = min(x+y,mini)
print(x-1+y-1)
### BUGGY CODE ###

n = int(input())
arr = []
for i in range(n-1):
    arr.append(tuple(map(int, input().split())))

for i in range(n-1):
    c1, s1, f1 = arr[i]
    ct = s1+c1
    for j in range(i+1, n-1):
        c2, s2, f2 = arr[j]
        while ct > s2:
            s2 += f2
        ct = s2 + c2
    print (ct)
print (0)

### FIXED CODE ###

n = int(input())
arr = []
for i in range(n-1):
    arr.append(tuple(map(int, input().split())))

for i in range(n-1):
    c1, s1, f1 = arr[i]
    ct = s1+c1
    for j in range(i+1, n-1):
        c2, s2, f2 = arr[j]
        while ct > s2:
            s2 += f2
        ct = s2 + c2
    print (ct)
print (0)
### BUGGY CODE ###

import collections
n,k=map(int,input().split())
A=list(map(int,input().split()))
c=collections.Counter(A)
tot=0
for i in range(min(k,len(set(A)))):
  tot+=c.most_common()[i][1]
print(n-tot)


### FIXED CODE ###

import collections
n,k=map(int,input().split())
A=list(map(int,input().split()))
c=collections.Counter(A)
tot=0
for i in c.most_common(min(k,len(set(A)))):
  tot+=i[1]
print(n-tot)