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

import sys
input = sys.stdin.readline

mod = 998244353

n, m, k = [int(x) for x in input().split()]

def make_tables(n, mod = 998244353):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 998244353):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

fac, finv = make_tables(n)
cal = m
ans = 0
for i in range(n - 1 - k):
    cal *= m - 1
    cal %= mod
ans += cal * nCk(n - 1, k)
ans %= mod
for i in range(1, k + 1):
    cal *= (m - 1)
    ans += cal * nCk(n - 1, k - i)
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

n, m, k = [int(x) for x in input().split()]

def make_tables(n, mod = 998244353):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod // i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 998244353):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

fac, finv = make_tables(n)
cal = m
ans = 0
for i in range(n - 1 - k):
    cal *= m - 1
    cal %= mod
ans += cal * nCk(n - 1, k)
ans %= mod
for i in range(1, k + 1):
    cal *= (m - 1)
    cal %= mod
    ans += cal * nCk(n - 1, k - i)
    ans %= mod
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

N = int(input())
P = list(map(float, input().rstrip().split(' ')))

dp = [[0] * (N + 1) for _ in range(N + 1)]

dp[0][0] = 1
for i in range(1, N + 1):
    dp[0][i] = (1.0 - P[i-1]) * dp[0][i-1]
    
for i in range(1, N + 1):
    for j in range(i, N + 1):
        dp[i][j] = dp[i-1][j-1] * P[j-1] + dp[i][j-1] * (1.0 - P[j-1])
        
print(sum([x[-1] for x in dp[-(N+1)//2:]]))


### FIXED CODE ###

# coding: utf-8
# Your code here!

import numpy as np

N = int(input())
P = list(map(float, input().rstrip().split(' ')))

dp = np.zeros((N+2, N+1))

dp[1,0] = 1
for i in range(0, N):
    dp[1:(i+3), i+1] += dp[0:(i+2), i] * P[i]
    dp[1:(i+3), i+1] += dp[1:(i+3), i] * (1.0 - P[i])
        
print(sum(dp[-(N+1)//2:, -1]))
### 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])
    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:
        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)     


### 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 ###

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


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i][i_w - item[0]] + item[1], dp[i][i_w])
            else:
                dp[i + 1][i_w] = dp[i][i_w]

    print(dp[n][w])


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    n, w = map(int, input().split())
    items = [tuple(map(int, input().split())) for i in range(n)]

    dp = [[0] * (w + 1) for i in range(n + 1)]

    for i, item in enumerate(items):
        for i_w in range(w + 1):
            if i_w >= item[0]:
                dp[i + 1][i_w] = max(dp[i][i_w - item[0]] + item[1], dp[i][i_w])
            else:
                dp[i + 1][i_w] = dp[i][i_w]

    print(dp[n][w])


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

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
A=[0]
if K!=1:
  for k in range(0,N-K+1):
    On=0
    for l in range(0,K):
      On+=P[k+l]
    A.append(On)
  print((max(A)+K)/2)
else:
  print((max(P)+1)/2)


### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(N):
  sum += i
print(sum)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))
score = []

temp = 1
for i in range(n):
    if i < k-1:
        temp *= data[i]
        score.append(0)
    elif i == k-1:
        temp *= data[i]
        score.append(temp)
    else:
        temp = temp // data[i-k] * data[i]
        score.append(temp)
    #print("i:{}, k:{}".format(i, k))
    #print(score)

    if i > k-1:
        if score[i] > score[i-1]:
            print("Yes")
        else:
            print("No")




### FIXED CODE ###

#!/usr/bin/env python3
# スペース区切りの整数の入力
n, k = map(int, input().split())
#配列の入力
data = list(map(int, input().split()))

for i in range(n-k):
    if data[i] < data[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import deque
n, m = list(map(int, input().split()))
connects = [[0] * n for _ in range(n)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    connects[i - 1][j - 1] = 1
    connects[j - 1][i - 1] = 1
stack = deque([0, ])
visited = [-1] * n
while stack:
    x = stack.popleft()
    connects_with_x = [i for i in range(n) if connects[x][i] == 1]
    for dx in connects_with_x:
        if visited[dx] == -1:
            visited[dx] = x
            stack.append(dx)
        else:
            continue
print('Yes')
[print(i + 1) for i in visited[1:]]

### FIXED CODE ###

from collections import deque
n, m = list(map(int, input().split()))
connects = [[] * n for _ in range(n)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    connects[i - 1].append(j - 1)
    connects[j - 1].append(i - 1)
stack = deque([0, ])
visited = [-1] * n
while stack:
    x = stack.popleft()
    for dx in connects[x]:
        if visited[dx] == -1:
            visited[dx] = x + 1
            stack.append(dx)
        else:
            continue
print('Yes')
[print(i) for i in visited[1:]]
### BUGGY CODE ###

se=input()
q=int(input())
h=0
for i in range(q):
    s=input().split()
    if len(s)==1:
        h+=1
    elif len(s)==3:
        if (h+int(s[1])-1)%2==0:
            se=s[2]+se
        else:
            se+=s[2]
if h%2==0:
    print(se)
else:
    print(se[::-1])

### FIXED CODE ###

se=input()
q=int(input())
h=0
se1=""
se2=""
for i in range(q):
    s=input().split()
    if len(s)==1:
        h+=1
    elif len(s)==3:
        if (h+int(s[1])-1)%2==0:
            se1+=s[2]
        else:
            se2+=s[2]
r=se1[::-1]+se+se2
if h%2==0:
    print(r)
else:
    print(r[::-1])
### BUGGY CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    print(0)
    exit()

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    print(N-1)
    exit()

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        print(mid)
        exit()

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left+1, m-1
    else:
        left, right = m+1, right-1


### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

S=str(input())
T=str(input())

ls=len(S)
lt=len(T)


DP=[[0]*(lt+1) for _ in range(ls+1)]


for i in range(1,ls+1):
    for j in range(1,lt+1):
        if S[i-1]==T[j-1]:
            DP[i][j]=max(DP[i-1][j-1]+1,DP[i][j-1],DP[i-1][j])
        else:
            DP[i][j]=max(DP[i][j-1],DP[i-1][j])

lf=DP[ls][lt]

res=''
u=ls
v=lt
while u>0 and v>0:
    if DP[u][v]==DP[u-1][v]:
        u-=1
    elif DP[u][v]==DP[u][v-1]:
        v-=1
    else:
        res=S[u-1]+res
        u-=1
        v-=1

print(res)

### FIXED CODE ###

S=str(input())
T=str(input())

ls=len(S)
lt=len(T)


DP=[[0]*(lt+1) for _ in range(ls+1)]


for i in range(1,ls+1):
    for j in range(1,lt+1):
        if S[i-1]==T[j-1]:
            DP[i][j]=max(DP[i-1][j-1]+1,DP[i][j-1],DP[i-1][j])
        else:
            DP[i][j]=max(DP[i][j-1],DP[i-1][j])

lf=DP[ls][lt]

res=''
u=ls
v=lt
while u>0 and v>0:
    if DP[u][v]==DP[u-1][v]:
        u-=1
    elif DP[u][v]==DP[u][v-1]:
        v-=1
    else:
        res=S[u-1]+res
        u-=1
        v-=1

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

n,m=[int(i) for i in input().split()]
min_money=[10000000000]
min_buy=[0]
for i in range(n):
    a,b=[int(i) for i in input().split()]
    if a<min_money[-1]:
        min_money.append(a)
        min_money.sort()
    if a in min_money:
        min_buy.insert(min_money.index(a),b)
ans=0
for i in range(len(min_buy)):
    if min_buy[i]>=m:
        ans+=min_money[i]*m
        break
    else:
        ans+=min_money[i]*min_buy[i]
        m-=min_buy[i]
print(ans)

### FIXED CODE ###

n,m=[int(i) for i in input().split()]
hoge=[tuple([int(i) for i in input().split()]) for j in range(n)]
hoge.sort()
ans=0
for i in range(len(hoge)):
    if hoge[i][1]>m:
        ans+=hoge[i][0]*m
        break
    else:
        ans+=hoge[i][0]*hoge[i][1]
        m-=hoge[i][1]
print(ans)
### BUGGY CODE ###

S = input()
T = input()
len_s = len(S)
ok = True
for i in range(len_s):
  for j in range(i+1, len_s):
    if (S[i] == S[j] and T[i] != T[j]) or (S[i] != S[j] and T[i] == T[j]):
      ok = False
      break
if ok:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

S = input()
T = input()
len_s = len(S)
ok = True
s_dict = {}
t_dict = {}
for i in range(len_s):
  if S[i] in s_dict and s_dict[S[i]] != T[i]:
    ok = False
    break
  if T[i] in t_dict and t_dict[T[i]] != S[i]:
    ok = False
    break
  s_dict[S[i]] = T[i]
  t_dict[T[i]] = S[i]
if ok:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N = int(input())
S = str(input())
a=0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if S[i]==S[j]:
                continue
            if S[j]==S[k]:
                continue
            if S[k]==S[i]:
                continue
            if k+i==2*j:
                continue
            if i<=j and j<=k: 
                a+=1
print(a)

### FIXED CODE ###

import math
N = int(input())
S = str(input())
r=0
g=0
b=0
error=0
n=0

if N%2==0:
    n=(N//2)-1
else:
    n=N//2

for i in range(N):
    if S[i]=='R':
        r+=1
    if S[i]=='G':
        g+=1
    if S[i]=='B':
        b+=1

for p in range(n+1):
    for i in range(N-(p*2)):
        if S[i]==S[i+p] or S[i+p]==S[i+2*p] or S[i]==S[i+2*p]:
            continue
        else:
            error+=1
d=r*g*b

print(d-error)
### BUGGY CODE ###

N = int(input())

A = [None for _ in range(N)]
for i in range(N):
    A[i] = list(map(int, input().split()))

#ワーシャルフロイド法で条件を満たすものがあるか確認
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(N-1):
    for j in range(i,N):
        is_edge = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

print(ans) 

### FIXED CODE ###

N = int(input())

A = [None for _ in range(N)]
for i in range(N):
    A[i] = list(map(int, input().split()))

#ワーシャルフロイド法で条件を満たすものがあるか確認
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(N-1):
    for j in range(i,N):
        is_edge = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

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

N,M = map(int, input().split())
L = []
R = []
for idx in range(M):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)

lst = []
result = 0
for idx in range(M):
    lst.append(range(L[idx],R[idx]+1))
for id in range(1,max(R)+1):
    flag = True
    for i in range(M):
        if (id in lst[i]) == False:
            flag = False
            break
    if flag == True:
        result += 1
print(result)

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
l,r = [], []
for i in range(m):
    a,b = MAP()
    l.append(a)
    r.append(b)

max_l = max(l)
min_r = min(r)
if min_r<max_l:
    print(0)
    exit()
print(min_r-max_l+1)
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        a = L[i]+L[j]
        l = N-j
        b = l-bisect.bisect_left(L[j+1:],a)
        cnt+=l-b
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        b = bisect.bisect_left(L,L[i]+L[j])
        cnt += b-j-1
print(cnt)
### BUGGY CODE ###


R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]

rcvs = rcvs

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = [[0 for _ in range(C)] for _ in range(R)]


for rcv in rcvs:
    rewards[rcv[0]][rcv[1]] = rcv[2]

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        dp[i+1][j+1][0] = max(dp[i][j+1])
        dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
        
        for k in range(4): # move downside without selecting
            candidate = dp[i+1][j][k]
            dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
        if reward > 0:
            for k in range(3):
                dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
print(max(dp[-1][-1]))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
import sys

R, C, K = map(int, input().split())
rcvs = [list(map(int, input().split())) for _ in range(K)]
rcvs = np.array(rcvs, dtype=np.int64)

@njit(i8(i8[:,:]), cache=True)
def main(rcvs):
    rewards = np.zeros((R, C), dtype=np.int64)
    
    for i in range(len(rcvs)):
        rewards[rcvs[i][0]-1][rcvs[i][1]-1] = rcvs[i][2]
    
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1][j+1][0] = max(dp[i][j+1])
            dp[i+1][j+1][1] = dp[i+1][j+1][0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1][j+1][k] = max(dp[i+1][j][k], dp[i+1][j+1][k])
            if reward > 0:
                for k in range(3):
                    dp[i+1][j+1][k+1] = max(dp[i+1][j][k]+reward,dp[i+1][j+1][k+1])
    return max(dp[-1][-1])

print(main(rcvs))
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

f = True
day = 1
while(f):
  done = set()
  nokori_games = 0
  
  for m in range(n):
    la = len(a[m])
    nokori_games += la
    if m in done:
      pass
    elif la:
      teki = a[m][0]
      jibun = m + 1
      if a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.add(m)
        done.add(teki - 1)
        nokori_games -= 1
      elif not len(a[teki - 1]):
        print(-1)
        sys.exit()
  if nokori_games:
    if not len(done):
      print(-1)
      sys.exit()
  else:
    print(day)
    sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

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

a = sorted(a)
p = list(set(a))

if len(p) <= k:
    print('0')
    exit()

j = 0
ans = [0 for _ in range(len(p))]
for i in range(len(p)):
    ans[i] += a.count(p[i])

ans = sorted(ans)

print(sum(ans[:len(p) - k]))

### FIXED CODE ###

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

a = sorted(a)
p = list(set(a))

if len(p) <= k:
    print('0')
    exit()

j = 0
ans = [0 for _ in range(len(p))]
ans[0] = 1
for i in range(1, n):
    if a[i] == a[i - 1]:
        ans[j] += 1
    else:
        j += 1
        ans[j] += 1

ans = sorted(ans)

print(sum(ans[:len(p) - k]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000000)
n=int(input())
h=list(map(int,input().split()))
def cost(place):
    if place==n-1:
        return 0
    if place==n-2:
        return abs(h[n-2]-h[n-1])
    if place<=n-3:
        a=abs(h[place]-h[place+2])+cost(place+2)
        b=abs(h[place]-h[place+1])+cost(place+1)
        x=min(a,b)
        return x
print(cost(0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)
n=int(input())
h=list(map(int,input().split()))
memory={}
def cost(place):
    if place in memory:
        return memory[place]
    if place==n-1:
        return 0
    if place==n-2:
        return abs(h[n-2]-h[n-1])
    if place<=n-3:
        a=abs(h[place]-h[place+2])+cost(place+2)
        b=abs(h[place]-h[place+1])+cost(place+1)
        x=min(a,b)
        memory[place]=x
        return x
print(cost(0))