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

n,m = map(int,input().split())
A = list(map(int,input().split()))
for _ in range(m):
  b,c = map(int,input().split())
  A.extend([c for _ in range(b)])
A.sort(reverse = True)

print(sum(A[:n]))



### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
C = []
for _ in range(m):
  b,c = map(int,input().split())
  C.append((c,b))
C.sort(reverse = True)

count = 0
for c,b in C:
  A.extend([c for _ in range(b)])
  count += b
  if count > n:
    break
A.sort(reverse = True)

print(sum(A[:n]))
### BUGGY CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
mx=max(a for a,b in ab)
dp=[float('inf')]*(h+1+mx)
dp[0]=0
for i in range(1,h+1+mx):
  dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))

### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
mx=max(a for a,b in ab)
dp=[10**10]*(h+1+mx)
dp[0]=0
for i in range(1,h+1+mx):
  dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

N = int(input(""))
A = input("").split()
A = [int(i) for i in A]
n = 1


for i in range(N):
    n = n * A[i]

if n > 10 ** 18:
    n = -1

print(n)



### FIXED CODE ###

N = int(input(""))
A = list(map(int, input("").split()))
n = 1

if 0 in A:
    print(0)
else:
    for i in range(N):
        n = n * A[i]
        if n > 10 ** 18:
            n = -1
            break

    print(n)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)
    roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)].add(i2)


    for i in range(n):
        print(len(set(roots[find(i)]) - friend[i] - foe[i]) - 1, end=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

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

import numpy as np

input()
arr = np.array(list(map(int, input().split())))
nums = set(arr)

res = 0
for n in nums:
    res = max(sum((arr < (n+2))[arr > (n-2)]), res)
print(res)

### FIXED CODE ###

from collections import defaultdict
n = input()
nums = list(map(int, input().split()))
dic = defaultdict(int)
for num in nums:
    dic[num] += 1
keys = sorted(list(dic.keys()))
cnt = 1
for key in keys:
    cnt = max(dic[key] + dic[key + 1] + dic[key - 1], cnt)
print(cnt)
### BUGGY CODE ###

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

A.sort()

ans = []
for i in range(N):
    if len(ans) == 0:
        ans.append(A.pop(0))
        continue

    (Ai, ai) = (0, 0)
    if abs(A[0]-ans[-1]) > abs(A[Ai]-ans[ai]):
        (Ai, ai) = (0, -1)
    if abs(A[-1]-ans[0]) > abs(A[Ai]-ans[ai]):
        (Ai, ai) = (-1, 0)
    if abs(A[-1]-ans[-1]) > abs(A[Ai]-ans[ai]):
        (Ai, ai) = (-1, -1)

    if ai == -1:
        ans.append(A.pop(Ai))
    else:
        ans.insert(0, A.pop(Ai))

anssum = 0
for i in range(len(ans)-1):
    anssum += abs(ans[i]-ans[i+1])

#print('ans', ans)
print(anssum)


### FIXED CODE ###

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

A.sort()

arr = []
arr.append(A[0])
arr.append(A[-1])
Atop = 1
Abtm = len(A) - 2
ans = arr[-1]-arr[0]
for i in range(len(A)-2):
    (Ai, ai) = (Atop, 0)
    if abs(A[Atop]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Atop, -1)
    if abs(A[Abtm]-arr[0]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, 0)
    if abs(A[Abtm]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, -1)

    #print('A[Ai]: ', A[Ai])
    #print(arr)
    ans += abs(A[Ai]-arr[ai])
    if ai == -1:
        arr[-1] = A[Ai]
    else:
        arr[0] = A[Ai]

    if Ai == Atop:
        Atop += 1
    else:
        Abtm -= 1


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

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM * pow(A[i], MOD - 2, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(LCM, A[i])
ans = 0
for i in range(N):
    ans += LCM * pow(A[i], MOD - 2, MOD)
print(ans%MOD)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
RGB=[0,0,0]
for i in range(N):
  if S[i]=="R":
    RGB[0]+=1
  if S[i]=="G":
    RGB[1]+=1
  if S[i]=="B":
    RGB[2]+=1
ans=RGB[0]*RGB[1]*RGB[2]    
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]
    t=k+k-i
    if s1==s2:
      continue
    if t<=N-1:
      s3=S[t]
      if s3!=s1 and s3!=s2:
        ans-=1      
print(ans)        

### FIXED CODE ###

N=int(input())
S=input()
ans=0
RGB=[0,0,0]
for i in range(N):
  if S[i]=="R":
    RGB[0]+=1
  if S[i]=="G":
    RGB[1]+=1
  if S[i]=="B":
    RGB[2]+=1
ans=RGB[0]*RGB[1]*RGB[2]    
for i in range(N-2):
  s1=S[i]
  for k in range(i+1,N-1):
    s2=S[k]
    t=k+k-i
    if s1==s2:
      continue
    if t<=N-1:
      s3=S[t]
      if s3!=s1 and s3!=s2:
        ans-=1      
print(ans)
### BUGGY CODE ###

(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] * 20001
for i in range(1, h + 1):
    dp[i] = 10**9
    for a, b in m:
        dp[i] = min(dp[i], dp[i-a]+b)
print(dp[h])


### FIXED CODE ###

(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    for a, b in m:
        dp[i] = min(dp[i], dp[max(i-a,0)]+b)
print(dp[-1])
### BUGGY CODE ###

N = int(input())
g = {}
for i in range(1, N+1):
    g[i] = []

cache = {}
def dfs(g,start,end):
    if cache.get((start,end),None) != None:
        #print(start,end)
        return cache[(start,end)]
        pass
    stack = [(start, [start], 0)]
    while stack:
        (v, path, length) = stack.pop()
        for next,l in g[v]:
            if next in path: continue
            if next == end:
                cache[(start,end)] = length + l
                return cache[(start,end)]
            else:
                stack.append((next, path + [next], length + l))

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    if (a,c) not in g[b]:
        g[b].append((a,c))
Q, K = map(int,input().split())

for q in range(Q):
    x, y = map(int,input().split())
    print(dfs(g,x,K) + dfs(g,K,y))

### FIXED CODE ###

N = int(input())
g = {i: [] for i in range(1, N+1)}    

l = [0] * (N + 1)

for i in range(N-1):
    a, b, c = map(int,input().split())
    g[a].append((b,c))
    g[b].append((a,c))

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

stack = [K]

while len(stack):
    v = stack.pop()
    for c,ln in g[v]:
        if l[c] != 0:
            continue
        l[c] = l[v] + ln
        stack.append(c)

for q in range(Q):
    x, y = map(int,input().split())
    print(l[x] + l[y])
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if(h>i>-1<j<w)-1or'.'<m[i][j]:break
   if d[t]>=p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
### BUGGY CODE ###

import itertools
import re

t = input()
t_re = t.replace('?', '.')
pattern = re.compile(t_re)
count_prev = 0
ans = ''

l = []
for v in itertools.product('PD', repeat=len(t)):
  s = ''.join(v)
  if re.match(pattern, s):
    l.append(s)

for t in l:
  count = 0
  count += t.count('D')
  count += t.count('PD')
  if count_prev < count:
    count_prev = count
    ans = t

print(ans)

### FIXED CODE ###

import itertools
import re
#from itertools import permutations, combinations,combinations_with_replacement,product

t = input()
#print(len(t))
print(t.replace('?', 'D'))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    score = 1
    for i in range(K):
        score *= A[i]

    prev_score = score
    for i in range(N-K):
        score //= A[i]
        score *= A[i+K]
        if score>prev_score:
            print(YES)
        else:
            print(NO)
        prev_score = score
    return


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

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    for i in range(N-K):
        if A[i]<A[i+K]:
            print(YES)
        else:
            print(NO)
    return


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

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

N = int(input())
S = input()

ans = 1e9
for i in range(N):
  tmp = 0
  l, r = S[:i], S[i+1:]
  tmp += l.count("W") + r.count("E")
  ans = min(ans, tmp)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
w = 0
e = S.count("E")
ans = e + w
for s in S:
  if(s == "E"):
    e -= 1
  else:
    w += 1
  ans = min(ans, e+w)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = input()

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

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

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  
  dp=[[[] for i in range(w)] for j in range(h)]
  dp[0][0].append(abs(a[0][0]-b[0][0]))
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      for k in dp[i-1][j]:
        dp[i][j].append(abs(k-c))
        dp[i][j].append(k+c)
      for k in dp[i][j-1]:
        dp[i][j].append(abs(k-c))
        dp[i][j].append(k+c)
      dp[i][j]=list(set(dp[i][j]))
  print(min(dp[h-1][w-1]))

if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    l, r = LR[i]
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i: i+2] == 'AC' else 0)
ans = [t[LR[i][1] - 1] - t[LR[i][0] - 1] for i in range(Q)]    

print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
s = input()
p = [set() for _ in range(100)]
sp = [set() for _ in range(n)]
k = int(s[-1])
sp[-1].add(k)
for j in range(n-2,1,-1):
    tmp = set(sp[j+1])
    tmp.add(int(s[j]))
    sp[j] = tmp
for x in range(n-2):
    for y in range(x,n-1):
        if x < y:
            tstr = str(s[x])+str(s[y])
            b2 = int(tstr)
            if len(p[b2]) > 0:
                pass
            else:
                p[b2] |= sp[y+1]
g =0
for c in p:
    g += len(c)
print(g)

### FIXED CODE ###

n = int(input())
s = input()
p = [set() for _ in range(100)]
sp = [set() for _ in range(n)]
k = int(s[-1])
sp[-1].add(k)
ful = False
for j in range(n-2,1,-1):
    if ful:
        sp[j] = {0,1,2,3,4,5,6,7,8,9}
    tmp = set(sp[j+1])
    if len(tmp) == 10:
        ful = True
    tmp.add(int(s[j]))
    sp[j] = tmp

s10 = [[99999 for _ in range(2)] for _ in range(10)]
for i,d in enumerate(s):
    c = int(d)
    if s10[c][0] == 99999:
        s10[c][0] = i
    elif s10[c][1] == 99999:
        s10[c][1] = i
g = 0
for i in range(10):
    for j in range(10):
        ans = 0
        nexid = min(s10[i])
        if nexid != 99999:
            for r in range(nexid+1,n-1):
                if int(s[r]) == j:
                    ans = len(sp[r+1])
                    break
            g += ans
print(g)
### BUGGY CODE ###

# coding: utf-8

#約数列挙
def enum_divisors(N):
    f = []
    i = 1
    #sqrt不使用: 少数誤差が気にならない
    while i * i <= N:
        if N % i == 0:
            f.append(i)
            if N//i != i:
                #重複しないならば、iの相方であるN/iも追加
                f.append(N//i)
        i += 1
    f.sort()
    return f

#main
X = int(input())
F = enum_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

if X == 1:
    print('0 -1')
else:
    for i in range(1, len(S)):
        tmp = S[i]
        for A in range(1, tmp):
            B = A - tmp
            if A**5 - B**5 == X:
                print(str(A) + ' ' + str(B))
                break
        else:
            continue
        break

### FIXED CODE ###

# coding: utf-8

#約数列挙
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

#main
X = int(input())
F = make_divisors(X)
#intのみのlistは、直接.join()できない
S = [int(x) for x in F]

for i in range(len(S)):
    tmp = S[i]
    for A in range(-1000, 1001):
        B = A - tmp
        if A**5 - B**5 == X:
            print(str(A) + ' ' + str(B))
            break
    else:
        continue
    break
### BUGGY CODE ###

N,M=map(int,input().split())
list1=[list(map(int,input().split())) for i in range(M)]
list2=list(range(N+1))
ans=set(range(N+1))
for i in range(M):
    lr=set(list2[list1[i][0]:list1[i][1]+1])
    #print(lr)
    ans=ans&lr
#print(ans)
print(len(ans))


### FIXED CODE ###

N,M=map(int,input().split())
list1=[list(map(int,input().split())) for i in range(M)]
start=[]
end=[]
for i in range(M):
    start.append(list1[i][0])
    end.append(list1[i][1])
stmax=max(start)
#print(stmax)
enmax=min(end)
#print(enmax)
if enmax>=stmax:
    print(enmax-stmax+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())

ans = []
n = 1
for _ in range(N):
    tmp = input()


    for a in ans:
        if a[0] == tmp:
            a[1] = a[1] + 1
            if a[1] > n:
                n = a[1]
            continue
    
    ans.append([tmp, 1])
last = []
for a in ans:
    if a[1] == n:
        last.append(a[0])
last.sort()
# print()
for l in last:
    print(l)

### FIXED CODE ###

N = int(input())

ans = {}
m = 1
for _ in range(N):
    w = input()
    c = ans.get(w)
    # print(c)
    # print(type(c))
    if c == None:
        ans[w] = 1
    else:
        ans[w] = c + 1
        if c + 1 > m:
            m = c + 1
# print(ans)

tmp = []
for a in ans:
    if ans[a] == m:
        tmp.append(a)

tmp.sort()
for t in tmp:
    print(t)
### BUGGY CODE ###

from collections import deque, defaultdict
from time import time

N = int(input())
A = [deque(map(lambda a: int(a) - 1, input().split())) for _ in range(N)]
S = time()

canBattle = defaultdict(lambda: False)
D = [0] * N

while True:
    isChanged = False
    for i, a in enumerate(A):
        if not a:
            continue
        j = a[0]
        canBattle[(i, j)] = True

        if canBattle[(j, i)]:
            isChanged = True
            A[i].popleft()
            A[j].popleft()
            d = max(D[i], D[j])
            D[i], D[j] = d + 1, d + 1
    if all(len(a) == 0 for a in A):
        print(max(D))
        exit()
    if time() - S >= 1950:
        print(N * (N - 1) // 2)
    if not isChanged:
        break

print(-1)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    N = int(input())
    A = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    days = [0] * (N + 1)
    now = [0] * (N + 1)

    que = deque([i + 1 for i in range(N)])

    while que:
        i = que.popleft()
        if not A[i]:
            continue

        a = A[i].popleft()
        if now[a] == i:
            days[a] = days[i] = max(days[a], days[i]) + 1
            que.append(i)
            que.append(a)
            now[a] = now[i] = 0
        else:
            now[i] = a

    for i in range(1, N + 1):
        if A[i]:
            print(-1)
            return
    print(max(days))


sol()
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q[0]=='1':
        S = S[::-1]
    if q[0]=='2':
        n, f= map(int, q[:-1].split())
        c = q[-1]
        if f==1:
            S = c + S
        if f==2:
            S = S + c
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
reverse = 0
left = ""
right = ""
for _ in range(Q):
    q = input().split()
    if q[0]=="1":
        reverse += 1
        left, right = right, left
    if q[0]=="2" and q[1]=="1":
        if reverse%2==0: left = q[2]+left
        else: left = left+q[2]
    if q[0]=="2" and q[1]=="2":
        if reverse%2==0: right = right+q[2]
        else: right = q[2]+right
if reverse%2==1:
    left = left[::-1]
    right = right[::-1]
    S = S[::-1]
print(left+S+right)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
K = int(input())
 
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        gcd_ij = np.gcd(i, j)
        for k in range(1, K + 1):
            ans += np.gcd(gcd_ij, k)

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K = int(input())

# lcm & gcd not math library
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

from functools import reduce
def gcd_multi(num_list):
    return reduce(gcd, num_list)

ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j and j == k:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += gcd_multi([i, j, k]) * dup_num

print(ans)