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

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    gamed = [0 for _ in range(N)]
    while 1:
        for i in range(N):
            gamed[i] = 0
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if j < i or gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
for i in range(n):
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*3**q
        y=a_count[i]*q_rcount[n-1-i]*3**(q-1)
        z=q_lcount[i]*c_count[n-1-i]*3**(q-1)
        w=q_lcount[i]*q_rcount[n-1-i]*3**(q-2)
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*3**(q-1)
        y=a_count[i]*q_rcount[n-1-i]*3**(q-2)
        z=q_lcount[i]*c_count[n-1-i]*3**(q-2)
        w=q_lcount[i]*q_rcount[n-1-i]*3**(q-3)
        ans=(ans+x+y+z+w)%INF
print(int(ans))


### FIXED CODE ###

s=input()
a_count=[0]
c_count=[0]
q_lcount=[0]
q_rcount=[0]
n=len(s)
for i in range(n):
    if s[i]=='A':
        a_count.append(a_count[i]+1)
        q_lcount.append(q_lcount[i])
    elif s[i]=='?':
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i]+1)
    else:
        a_count.append(a_count[i])
        q_lcount.append(q_lcount[i])
    if s[n-1-i]=='C':
        c_count.append(c_count[i]+1)
        q_rcount.append(q_rcount[i])
    elif s[n-1-i]=='?':
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i]+1)
    else:
        c_count.append(c_count[i])
        q_rcount.append(q_rcount[i])
q=q_lcount[n]
ans=0
INF=10**9+7
a=3**q
b=a//3
c=b//3
d=c//3
a=a%INF
b=b%INF
c=c%INF
d=d%INF
for i in range(n):
    if s[i]=='B':
        x=a_count[i]*c_count[n-1-i]*a
        y=a_count[i]*q_rcount[n-1-i]*b
        z=q_lcount[i]*c_count[n-1-i]*b
        w=q_lcount[i]*q_rcount[n-1-i]*c
        ans=(ans+x+y+z+w)%INF
    elif s[i]=='?':
        x=a_count[i]*c_count[n-1-i]*b
        y=a_count[i]*q_rcount[n-1-i]*c
        z=q_lcount[i]*c_count[n-1-i]*c
        w=q_lcount[i]*q_rcount[n-1-i]*d
        ans=(ans+x+y+z+w)%INF
print(int(ans))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

from bisect import bisect_left

def rsort(b,k):
    b0 = []
    b1 = []
    for i in b:
        if i&(1<<k):
            b1.append(i)
        else:
            b0.append(i)
    return b0+b1
    
def f(a,k,bisect_left): #k桁目のxor
    global b
    p1 = 1<<k
    p2 = p1<<1
    p3 = p1+p2

    b = rsort(b,k)
    #print(b)
    
    bb = [i&(p2-1) for i in b]
    
    res = 0
    for ai in a:
        ai &= (p2-1)
        if p1-ai<0:
            j1 = 0
        else:
            j1 = bisect_left(bb,p1-ai)

        j2 = bisect_left(bb,p2-ai)
        
        if p3 - ai > bb[-1]:
            j3 = n
        else:
            j3 = bisect_left(bb,p3-ai)
        
        res += j2-j1+n-j3
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    return (res&1)<<k


ans = 0

for k in range(29):
    ans |= f(a,k,bisect_left)

print(ans)    









### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]

from bisect import bisect_left


ans = 0

for k in range(29):
    a0 = []
    a1 = []
    a0a = a0.append
    a1a = a1.append
    
    b0 = []
    b1 = []
    b0a = b0.append
    b1a = b1.append
    for i in a: #基数ソート
        if i&(1<<k): a1a(i)
        else: a0a(i)
    for i in b: #基数ソート
        if i&(1<<k): b1a(i)
        else: b0a(i)
    
    a = a0+a1
    b = b0+b1
    mask = (1<<(k+1))-1
    
    aa = [i&mask for i in a]
    bb = [i&mask for i in b]
    
    res = 0
    p1 = 1<<k
    p2 = mask+1
    p3 = p1+p2

    j1=j2=j3=0    
    for ai in reversed(aa):
        while j1 < n and ai+bb[j1] < p1:
            j1 += 1
        while j2 < n and ai+bb[j2] < p2:
            j2 += 1
        while j3 < n and ai+bb[j3] < p3:
            j3 += 1
        res += j2-j1+n-j3
        #if k < 3: print(ai,p2,res,bb,j1,j2,j3,n)
        #print(bb,p2,ai,j1,j2,j3,n,"R",res)    
    ans |= (res&1)<<k
    



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

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

l = 0
r = max(a * f for a, f in zip(A, F)) + 1

while l < r:
    m = (l + r) // 2
    if sum(max(a - m // f, 0) for a, f in zip(A, F)) <= K:
        r = m
    else:
        l = m + 1

print(r)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)
A.sort()
F.sort()
F = F[::-1]

l = 0
r = (A * F).max()

while l < r:
    m = (l + r) // 2
    if np.maximum(A - m // F, 0).sum() <= K:
        r = m
    else:
        l = m + 1

print(r)
### BUGGY CODE ###

N = int(input())

ans=0
for i in range(1,N+1):
	n=N//i
	ans+=int(i*(n+1)*n/2)

print(ans)

# 2darray [[0] * 4 for i in range(3)]
# import itertools

### FIXED CODE ###

N = int(input())

ans=0
for i in range(1,N+1):
	n=N//i
	ans+=i*(n+1)*n/2

print(int(ans))

# 2darray [[0] * 4 for i in range(3)]
# import itertools
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for l in range(k+1):
  for n in range(k+1):
    for m in range(k+1):
      if l+n+m==s: ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        if 0 <= s-i-j <= k: ans += 1
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
m = a*b
for i in range(1, m+1):
  if i%a==0 and i%b==0:
    print(i)
    break

### FIXED CODE ###

a, b = map(int, input().split())
aa = []
bb = []

count = 2

while True:
  if a == 1:
    aa.append(a)
    break
  if a%count == 0:
    aa.append(count)
    a = a//count
  else:
      count += 1
    
count = 2

while True:
  if b == 1:
    bb.append(b)
    break
  if b%count == 0:
    bb.append(count)
    b = b//count
  else:
      count += 1
answer = 1
c = set(aa) | set(bb)
for i in c:
  answer *= i ** max(aa.count(i), bb.count(i))
print(answer)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
cost=[0]
for i in range(1,n):
  wk=[]
  for j in range(1,min(k,i)+1):
    wk.append(cost[i-j]+abs(h[i]-h[i-j]))
  cost.append(min(wk))
print(cost[n-1])

### FIXED CODE ###

from numba import jit
n,k=map(int,input().split())
h=list(map(int,input().split()))
@jit
def jitcalc(n,k,h):
  cost=[0]
  for i in range(1,n):
    wk=[]
    for j in range(1,min(k,i)+1):
      wk.append(cost[i-j]+abs(h[i]-h[i-j]))
    cost.append(min(wk))
  print(cost[n-1])
jitcalc(n,k,h)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

idx = -1
m = 0
for i in range(n-k+1):
    s = sum(p[i:i+k])
    if m < s:
        m = s
        idx = i

ans = 0
for i in p[idx:idx+k]:
    ans += (i - 1) * 0.5 + 1
print('{:.12f}'.format(float(ans)))


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
p = [(int(i) + 1) * 0.5 for i in input().split()]
m = sum(p[:k])
s = m
for i in range(k, n):
    s = s + p[i] - p[i-k]
    m = max(m, s)
print('{:.7f}'.format(m))
### BUGGY CODE ###

s = input()
cnt = 0
pass_ = False
for start in range(len(s)):
  end = start + 3
  if int(s[start:end+1]) == 2019:
    cnt += 1
    pass_ = True
  elif int(s[start:end+1]) < 2019:
    end += 1
  while(end+1<=len(s)):
    if int(s[start:end+1]) % 2019 == 0 and pass_ == False:
      cnt += 1
    end += 1
    pass_ = False
print(cnt)


### FIXED CODE ###

s = input()
l = len(s)
dp = [0]*2019
dp[0] = 1
r = 0
for i in range(1, l + 1):
    r += int(s[-i]) * pow(10, i - 1, 2019)
    r %= 2019
    dp[r] += 1
    
print(sum([(i * (i - 1)) // 2 for i in dp]))
### BUGGY CODE ###

n,m=map(int, input().split())
ans=set()
for i in range(m):
    l,r=map(int, input().split())
    if i==0:
        ans=set(range(l,r+1))
    else:
        tmp=set(range(l,r+1))
        ans=ans & tmp

print(len(ans))

### FIXED CODE ###

n,m=map(int, input().split())
l_ans=1
r_ans=n
for i in range(m):
    l,r=map(int, input().split())
    l_ans=max(l_ans,l)
    r_ans=min(r_ans,r)

if r_ans>=l_ans:
    print(r_ans-l_ans+1)
else:
    print(0)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))

ans=0
cnt=0
for j in range(n*n//2+1):
    f=0
    q=[0]*n
    for i in range(n):        
        if len(a[i])>0 and len(a[a[i][0]-1])>0 and i+1==a[a[i][0]-1][0] and i<a[i][0]-1 and q[a[i][0]-1]==0 and q[i]==0:
            q[a[i][0]-1]+=1
            q[i]+=1
            
            a[a[i][0]-1].pop(0)
            a[i].pop(0)
            
            #q.append(i)
            #q.append(a[i][0]-1)
            f+=1    
            cnt+=1
    #if len(q)>0:
        #for k in q:
            #a[k].pop(0)
            
            
    if f==0 and cnt<n*(n-1)//2:
        print(-1)
        exit()
    elif f>0:
        ans+=1
    else:
        print(ans)
        exit()


### FIXED CODE ###

from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())

q = [[]]
l = [0] * 1005
d = [0] * 1005
hv = [0] * 1005

def dfs(x,y):
    hv[x] = 1
    for i in range(l[x],n-1):

        if q[x][i] == y:
            l[x] = i+1
            hv[x] = 0

            d[q[x][i]] += 1
            d[x] += 1
            d[x] = max(d[x],d[q[x][i]])
            d[q[x][i]] = max(d[x], d[q[x][i]])

            return
        if hv[q[x][i]]:
            print(-1)
            exit(0)
        dfs(q[x][i],x)
        d[x] = max(d[q[x][i]],d[x])


    hv[x] = 0
    l[x] = n

n = int(input())
for i in range(n):
    a = list(rrd())
    q.append(a)

for i in range(1,n+1):
    dfs(i,0)

print(max(d))
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans1,ans2=0,0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            ans1+=1
for i in range(2*n-1):
    for j in range(i+1,2*n):
        if a[i%n]>a[j%n]:
            ans2+=1
print((ans1*((1+k)*k)//2+(ans2-3*ans1)*((1+(k-1))*(k-1))//2)%(10**9+7))

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans1 = 0
ans3 = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]>a[j]:
            ans1+=1
        elif a[i]==a[j]:
            ans3+=1
ans2 = (n*(n-1))//2 - ans1 - ans3
print((ans1*((1+k)*k)//2+ans2*(k*(k-1))//2)%(10**9+7))
### BUGGY CODE ###

import copy

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

N = 13
MOD = 1000000000 + 7
s = input()
dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
dp[0] = 1
rs = reversed(s)

for i, si in enumerate(rs):
    nextdp = [0 for j in range(N)]

    for j in range(10):
        c = 0
        if si == "?":
            c = (j * 10 ** i) % N
        elif j == 0:
            c = (int(si) * 10 ** i) % N
        else:
            break

        for k in range(N):
            nextdp[(k + c) % N] += dp[k]
            nextdp[(k + c) % N] %= MOD

    dp = copy.copy(nextdp)

print(dp[5])


### FIXED CODE ###

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

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])
### BUGGY CODE ###

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


if k == 1:
    n = 0
else:
    while True:
        if abs(k - n) < n:
            n = abs(k - n)
        else:
            FLG = True
            break

print(n)

### FIXED CODE ###

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

if n >= k:
    n -= k * (n // k)      

if k-n > n:
    print(n)
else:
    print(k-n)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i,n):
        if abs(i-j)==a[i]+a[j]:
            ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

#ref = dict(Counter(r))
#ans = 0
#for i in l:
#    ans += ref.get(i, 0)
#print(ans)
b=Counter(r)
for i in l:
    ans+=b.get(i,0)

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

n,m = map(int,input().split())
ls = list(map(int,input().split()))
dir = [list(map(int,input().split())) for _ in range(m)]
k = 0
p = 0
for i in range(1,n+1):
    new = [e for e in dir if i in e]
    if new == []:
        k += 1
    else:
        for j in range(len(new)):
            if new[j][0] != i:
                (new[j][0],new[j][1]) = (new[j][1],new[j][0])
            if ls[new[j][0]-1]>ls[new[j][1]-1]:
                p += 1
            if p == len(new):
                k += 1
        p = 0
print(k)
                


### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
pos = [1]*(n)
for i in range(m):
    a,b = map(int,input().split())
    if ls[a-1] > ls[b-1]:
        pos[b-1] = 0
    elif ls[a-1] < ls[b-1]:
        pos[a-1] = 0
    else:
        pos[a-1] = 0
        pos[b-1] = 0
print(sum(pos))
### BUGGY CODE ###

import sys

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_attend_stu = []
list_stu_Serial_Num = list(range(1, Num + 1))
list_stu_Num_index = list(range(Num))
for i in list_stu_Serial_Num:
    for l in list_stu_Num_index:
        if list_stu_Num[l] == str(i):
            list_attend_stu.append(l + 1)
print(*list_attend_stu)

### FIXED CODE ###

import sys
import numpy as np

Num = int(sys.stdin.readline().rstrip())
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
print(*np.argsort(list_stu_Num_int) + 1)
### BUGGY CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

    aa = list(map(int, input().split()))

    """

    n = 100000
    k = 50000
    aa = [i for i in range(100000)]
    """

    import math

    if k == 1:
        print(0)
    else:
        aa.sort()

        cnt = 0

        c = 1
        large = k+1
        before = 0

        for i, j in zip(aa[k-1:], reversed(aa[:-k+1])):
            cnt += (i-j)*(c-before)
            cnt = cnt%(10**9+7)
            before = c
            c = c*large//(large-k)
            large += 1
            """
            if math.isnan(cnt):
                print(c, large, k, before, i, j)
                break
            """

        print(int(cnt%(10**9+7)))


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

    aa = list(map(int, input().split()))

    """

    n = 100000
    k = 50000
    aa = [i for i in range(100000)]
    """

    import math

    if k == 1:
        print(0)
    else:
        def cmb(n, r, p):
            if (r < 0) or (n < r):
                return 0
            r = min(r, n - r)
            return fact[n] * factinv[r] * factinv[n-r] % p

        p = 10 ** 9 + 7
        N = 10 ** 5  # N は必要分だけ用意する
        fact = [1, 1]  # fact[n] = (n! mod p)
        factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
        inv = [0, 1]  # factinv 計算用

        for i in range(2, N + 1):
            fact.append((fact[-1] * i) % p)
            inv.append((-inv[p % i] * (p // i)) % p)
            factinv.append((factinv[-1] * inv[-1]) % p)

        aa.sort()

        cnt = 0

        c = 1
        large = k
        before = 0

        for i, j in zip(aa[k-1:], reversed(aa[:-k+1])):
            c = cmb(large, k, p)
            cnt += (i-j)*(c-before)
            cnt = cnt%(10**9+7)
            before = c
            large += 1

        print(int(cnt%(10**9+7)))
### BUGGY CODE ###

from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
s = [ input() for _ in range(n) ]

# def mycheck(a,b):
#     b = list(b)
#     for i in range(len(a)):
#         if a[i] in b:
#             b.remove(a[i])
#         else:
#             return False
#     return True
ls = []
for i in range(n):
    t = Counter(s[i])
    ls.append(t)
# print(ls)

count = 0
for i in range(n):
    for j in range(i+1,n):
        if ls[i]==ls[j]:
            count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
# print(n)
# print(s)
s = list(map(list, s))
# print(s)
for i in range(n):
    s[i].sort()
    s[i] = "".join(s[i])
# print(s)
dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic.setdefault(s[i],1)
a = list(dic.values())
# print(a)
import math
count = 0
for i in range(len(a)):
    if a[i] >= 2:
        count += math.factorial(a[i])//(math.factorial(a[i]-2)*2)
print(count)
### BUGGY CODE ###

n,w=map(int,input().split())
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])
INF=float('inf')
 
dp=[[0 for i in range(w+1)] for j in range(n+1)]
 
for i in range(1,n+1):
  for j in range(1,w+1):
    if j-P[i-1][0]>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-P[i-1][0]]+P[i-1][1])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[n][w])

### FIXED CODE ###

n,w=map(int,input().split())
P=[]
for _ in range(n):
  iw,iv=map(int,input().split())
  P.append([iw,iv])
INF=float('inf')
 
dp=[[0 for i in range(w+1)] for j in range(n+1)]
 
for i in range(1,n+1):
  for j in range(1,w+1):
    if j-P[i-1][0]>=0:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-P[i-1][0]]+P[i-1][1])
    else:
      dp[i][j]=dp[i-1][j]
print(dp[n][w])
### BUGGY CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

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

ki = [0] * len(A)
xv = A.copy()

def max_index(v):
    max_i = 0
    for i in range(len(v)):
        if (v[i]>v[max_i]):
            max_i = i
    return max_i

dprint("ki", ki)
dprint("xv", xv)
for i in range(k):
    max_i = max_index(xv)
    ki[max_i] += 1
    xv[max_i] = A[max_i] / (ki[max_i] + 1)
    dprint("max_i", max_i)
    dprint("ki", ki)
    dprint("xv", xv)
    
ans = math.ceil(max(xv))
print(ans)


### FIXED CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
dprint("n, k = ", n, k)

lx = int(0)   # NG
rx = int(1e9) # OK
#ans = 0
while ((rx-lx)>1):
    x = (rx + lx) // 2
    dprint("lx, x, rx = ", lx, x, rx)
    n = 0
    for i in range(len(A)):
        #n += math.ceil(A[i] / x) - 1
        n += (A[i]-1) // x
        if n > k: break
    dprint("n = ", n)
    if n <= k:
        dprint(" smaller x")
        rx = x
    else:
        dprint(" cut less, bigger x")
        lx = x

#ans = math.ceil(rx)
print(rx)
### BUGGY CODE ###

s = input()
K = int(input())
sSet = set()
for i in range(len(s)):
    for j in range(len(s)):
        sSet.add(s[i : j+1])
list = list(sSet)
list.sort()
try:
    list.remove("")
except:
    pass
print(list[K - 1])


### FIXED CODE ###

s = input()
K = int(input())
list = ["zzz" for i in range(K)]
for i in range(len(s)):
    for j in range(len(s)-i):
        if j > 5:
            continue
        if len(list) < K or s[i : i+j+1] < list[K-1]:
            if not s[i : i+j+1] in list:
                list[K-1] = s[i : i+j+1]
                list.sort()
print(list[K - 1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
flag=1

l=a
for i in a:
  if i==flag:
    flag+=1
  else:
    l=a[1:]
    count+=1
if count==n:
  print(-1)
else:
  print(count)




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
flag=1

l=a
left=0
for i in range(n):
  if l[i]==flag:
    flag+=1
  else:
    count+=1
    
if count==n:
  print(-1)
else:
  print(count)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort(reverse=True)
if n<k:
    for i in range(n):
        del h[0]
else:
    for i in range(k):
        del h[0]
print(sum(h))


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
h.sort(reverse=True)
if n<k:
    del h[0:n]
else:
    del h[0:k]
print(sum(h))