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

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wl,vl=[],[]
wsum=0
for i in range(n):
  wn,v=map(int, input().split())
  wl.append(wn)
  vl.append(v)
  wsum+=w
if wsum<w:
  w=wsum

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

for wsum in range(wmin,w+1):
  #print("重さ：{}".format(wsum))
  for i in range(n):
    #print("i={}".format(i))
    if wsum-wl[i]>=0:
      if dp[i+1][wsum] < dp[i][wsum-wl[i]]+vl[i]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)
dp=np.array(dp)
print(np.max(dp))
      


### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

n = int(input())
a = [input() for _ in range(n)]
b = []
a.sort()
for i in range(n):
    if a[i] not in b:
        b.append(a[i])
b.sort()
c = [0]*len(b)
for i in range(len(b)):
    c[i] += a.count(b[i])
for i in range(len(b)):
    if c[i] == max(c):
        print(b[i])


### FIXED CODE ###

n = int(input())
a = [input() for _ in range(n)]
cnt = {}
for i in range(n):
    if a[i] not in cnt:
        cnt[a[i]] = 1
    else:
        cnt[a[i]] += 1
mx = max(cnt.values())
ans = []
for i in cnt.keys():
    if cnt[i] == mx:
        ans.append(i)
ans.sort()
for _ in ans:
    print(_)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]


BB = [0] * N
for i in range(N):
    for c in C:
        if B[i] < c:
            BB[i] += 1

AA = [0] * N
for i in range(N):
    for j in range(N):
        if A[i] < B[j]:
            AA[i] += BB[j]

print(sum(AA))


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

A = sorted(A)
B = sorted(B)
C = sorted(C)

BB = [0] * N

cidx = 0
for i in range(N):
    while cidx < N and C[cidx] <= B[i]:
        cidx += 1
    BB[i] = N - cidx

BBB = [0] * N
for i in range(N - 1, -1, -1):
    if (i == N - 1):
        BBB[i] = BB[i]
    else:
        BBB[i] = BB[i] + BBB[i+1]

sum = 0
bidx = 0
for i in range(N):
    while bidx < N and B[bidx] <= A[i]:
        bidx += 1
    if bidx != N:
        sum += BBB[bidx]

print(sum)
### BUGGY CODE ###

N,A,B,K = map(int,input().split())
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
#fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
#    fac_inv.append(inv(f))

def ncr(n,r):
    return mul(mul(fac[n], inv(fac[n-r])), inv(fac[r]))

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp = mul(tmp, ncr(N, red+green+blue))
        tmp = mul(tmp, ncr(red+green+blue, green+blue))
        tmp = mul(tmp, ncr(green+blue, blue))
        ans += tmp
print(ans % MOD)


### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

def main():
    s = input()[::-1]

    sum_of_digits = 0

    cnts = [0] * 2019

    cnts[0] = 1

    for i in range(len(s)):
        sum_of_digits += int(s[i]) * pow(10, i)
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1

    ans = 0

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()[::-1]

    sum_of_digits = 0

    cnts = [0] * 2019

    cnts[0] = 1

    d = 1

    for i in range(len(s)):
        sum_of_digits += int(s[i]) * d
        d *= 10
        d %= 2019
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1


    ans = 0

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2

    print(ans)

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

x = int(input())

i = 1
a = 1
b = 0
while a**5 - b**5 <= x:
    if a**5 - b**5 == x:
        print(a, b)
        exit
    a += 1
    b -= 1

while True:
    i += 1
    if x % i:
        continue

    b = 1
    a = i - b
    while b < a and a**5 - b**5 <= x:
        if a**5 - b**5 == x:
            print(a, b)
            exit
        a += 1
        b -= 1

    a = i
    b = 0
    while a**5 - b**5 <= x:
        if a**5 - b**5 == x:
            print(a, b)
            exit
        a += 1
        b -= 1

### FIXED CODE ###

x = int(input())
OP = [+1, -1]
for a in range(1000):
    for b in range(a + 1):
        for op1 in OP:
            for op2 in OP:
                if (op1 * a)**5 - (op2 * b)**5 == x:
                    print(op1 * a, op2 * b)
                    exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

N = int(input())

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

col = [ -1 for i in range(N)]

col[0] = 0

p = []
def dfs(n,c,path):
    global p
    path = path + [n]
    if n == N - 1:
        p = path
    for v in e[n]:
        if col[v] == -1:
            col[v] = c + 1
            dfs(v,c+1,path)
dfs(0,0,[])

if len(p) % 2 ==0:
    fn = p[len(p)//2-1]
    sn = p[len(p)//2]
else:
    fn = p[len(p)//2]
    sn = p[len(p)//2+1]


colfn = [ -1 for i in range(N)]
colfn[0] = 0
def dfs2(n,c):

    for v in e[n]:
        if v == sn:
            continue
        elif colfn[v] == -1:
            colfn[v] = c + 1
            dfs2(v,c+1)

dfs2(0,0)

colsn = [ -1 for i in range(N)]
colsn[N-1] = 0
def dfs3(n,c):

    for v in e[n]:
        if v == fn:
            continue
        elif colsn[v] == -1:
            colsn[v] = c + 1
            dfs3(v,c+1)

dfs3(N-1,0)
fennec = -1
snuke = -1
for i in range(N):
    if colsn[i] != -1:
        snuke += 1
    if colfn[i] != -1:
        fennec += 1

if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")

### FIXED CODE ###

import sys

p = []
path = [ 0 for i in range(10**5+1)]
def main():

    sys.setrecursionlimit(1000000)

    N = int(input())

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

    col = [ -1 for i in range(N)]
    col[0] = 0
    
    #def dfs(n,c,path):
    def dfs(n,c):
        global p
        #path =  path  + [n]
        #path.append(n)
        #print(path)
        if n == N - 1:
            p = path
        path[c] = n
        for v in e[n]:
            if col[v] == -1:
                col[v] = c + 1
                dfs(v,c+1)
                #dfs(v,c+1,path)
                if p:
                    return
    dfs(0,0)
    #print(p[:N+10])
    #dfs(0,0,[])

    t = col[N-1] + 1
    if t % 2 ==0:
        sn = p[t//2]
    else:
        sn = p[t//2+1]


    colfn = [ -1 for i in range(N)]
    colfn[0] = 0
    def dfs2(n,c):

        for v in e[n]:
            if v == sn:
                continue
            elif colfn[v] == -1:
                colfn[v] = c + 1
                dfs2(v,c+1)

    dfs2(0,0)

    fennec = -1
    for i in range(N):
        if colfn[i] != -1:
            fennec += 1

    snuke = N - fennec - 2
    if fennec > snuke:
        print("Fennec")
    else:
        print("Snuke")



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

MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = (LR[i-1] + 1) % 2
    else:
        LR[i] = LR[i-1]
if LR.count(0) != LR.count(1):
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)

### FIXED CODE ###

MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
l, r = 1, 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = 0 if LR[i-1] == 1 else 1
    else:
        LR[i] = LR[i-1]
    if LR[i] == 0:
        l += 1
    else:
        r += 1
if l != r:
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        count %= MOD
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)
### BUGGY CODE ###

n = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
p = 10 ** 9 + 7

B = [10**9] * n

if max(T) != max(A):
    print(0)
    exit()

h = 0

for i, t in enumerate(T):
    if h < t:
        B[i] = 1
        h = t
    else:
        B[i] = h

h = 0

for i, a in zip(range(n-1, -1, -1), A[::-1]):
    if h < a:
        B[i] = 1
        h = a
    elif B[i] == 1 and T[i] > A[i]:
        print(0)
        exit(0)
    elif B[i] > h:
        B[i] = h

ans = 1

for b in B:
    ans *= b

print(ans%p)

### FIXED CODE ###

n = int(input())
T = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
p = 10 ** 9 + 7

B = [10**9] * n

if max(T) != max(A):
    print(0)
    exit()

h = 0

for i, t in enumerate(T):
    if h < t:
        B[i] = 1
        h = t
    else:
        B[i] = h

h = 0

for i, a in zip(range(n-1, -1, -1), A[::-1]):
    if h < a:
        B[i] = 1
        h = a
    elif B[i] == 1 and T[i] > A[i]:
        print(0)
        exit(0)
    elif B[i] > h:
        B[i] = h

ans = 1

for b in B:
    ans *= b
    ans %= p

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

H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [[0 for _ in range(H * W)] for _ in range(H * W)]

for i in range(H * W):
	for j in range(i, H * W, d):
		num = 0
		for k in range(i, j, d):
			num += cost[k]
		ans[i][j] = num

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[l-1][r-1])

### FIXED CODE ###

H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])
### BUGGY CODE ###

x,y,a,b,c=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
A=A[:x]
B=B[:y]
A.sort()
B.sort()

i=0
j=0
k=0
lea=len(A)
leb=len(B)
while(True):
    if len(C)<1:
        break
    if i<lea and j<leb:
        if A[i]>B[j]:
            if B[j]<C[0]:
                B[j]=C.pop(0)
                
                j+=1
            else:
                break
        else:
            if A[i]<C[0]:
                A[i]=C.pop(0)
                i+=1
            else:
                break
    elif i<lea and j>=leb:
        if A[i]<C[0]:
                A[i]=C.pop(0)
                i+=1
        else:
            break
    elif i>=lea and j<leb:
        if B[j]<C[0]:
                B[j]=C.pop(0)
                j+=1
        else:
            break
    else:
        break
sum=0


for s in range(len(A)):
    sum+=A[s]
for t in range(len(B)):
    sum+=B[t]
print(sum)
     

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort(reverse=True)
A=A[a-x:]
B=B[b-y:]

i=0
j=0
k=0
lea=len(A)
leb=len(B)
while(True):
    if len(C)<1:
        break
    if i<lea and j<leb:
        if A[i]>B[j]:
            if B[j]<C[0]:
                B[j]=C.pop(0)
                
                j+=1
            else:
                break
        else:
            if A[i]<C[0]:
                A[i]=C.pop(0)
                i+=1
            else:
                break
    elif i<lea and j>=leb:
        if A[i]<C[0]:
                A[i]=C.pop(0)
                i+=1
        else:
            break
    elif i>=lea and j<leb:
        if B[j]<C[0]:
                B[j]=C.pop(0)
                j+=1
        else:
            break
    else:
        break
sum=0


for s in range(len(A)):
    sum+=A[s]
for t in range(len(B)):
    sum+=B[t]
print(sum)
### BUGGY CODE ###

S = input()
T = input()

len_S = len(S)
S_Converted = S
for i in range (len(S)):
    tmp_S = S_Converted[i]
    tmp_T = T[i]
    if tmp_S == tmp_T:
        continue
    S_Converted = list(S_Converted) 
    list_indexT = [j for j, tmp_SC in enumerate(S_Converted) if tmp_SC == tmp_T]
    
    S_Converted = ''.join(S_Converted)
    #print(tmp_S)
    S_Converted = S_Converted.replace(tmp_S, tmp_T)
    #print(S_Converted)
    S_Converted = list(S_Converted) 
    
    for li in list_indexT:
        if li == i:
            continue
        else:
            S_Converted[li] = tmp_S
    #print(''.join(S_Converted))
    
S_Converted = ''.join(S_Converted)

if S_Converted == T:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys

S = input()
T = input()

len_S = len(S)
S_Converted = S
for i in range (len(S)):
    tmp_S = S_Converted[i]
    tmp_T = T[i]
    if tmp_S == tmp_T:
        continue
    S_Converted = list(S_Converted) 
    list_indexT = [j for j, tmp_SC in enumerate(S_Converted) if tmp_SC == tmp_T]
    if (not list_indexT == []) and (list_indexT[0] < i):
        print('No')
        sys.exit()
    S_Converted = ''.join(S_Converted)
    S_Converted = S_Converted.replace(tmp_S, tmp_T)
    S_Converted = list(S_Converted) 
    for li in list_indexT:
        if li == i:
            continue
        else:
            S_Converted[li] = tmp_S
    #print(''.join(S_Converted))
    
S_Converted = ''.join(S_Converted)

if S_Converted == T:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

sumAB = sorted([ai + bi for ai in a for bi in b],reverse=True)
sumABC = sorted([ci + abi for ci in c for abi in sumAB],reverse = True)

for i in range(k):
    print(sumABC[i])

### FIXED CODE ###

x,y,z,k = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)

sumAB = sorted([ai + bi for ai in a for bi in b],reverse=True)[:k]
sumABC = sorted([ci + abi for ci in c for abi in sumAB],reverse = True)[:k]

for i in range(k):
    print(sumABC[i])
### BUGGY CODE ###

from functools import reduce

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    

    N = int(input().rstrip())
    # A = list(int(_) for _ in input().split())
    A = list(input().split())
    s_num = N -1
    ans = 2**(N//2)
    while s_num > 0:
        count = A.count(str(s_num))
        if(s_num != 0 and count != 2):
            ans = 0 
            break
        elif(s_num == 0 and count !=1):
            ans = 0 
            break
        s_num -= 2
    
    print(ans)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import reduce
import bisect

def main():
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10

    # mod用
    p=10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    

    N = int(input().rstrip())
    # A = list(map(int, input().split()))
    A = list(int(_) for _ in input().split())
    # A = list(input().split())
    A.sort()
    flag = False
    if A[0] == 0 and N%2 == 1:
        flag = True
        for i in range(N):
            if A[i] != (i + 1) // 2 * 2:
                flag = False
                break
    if A[0] == 1 and N%2 == 0:
        flag = True
        for i in range(N):
            if A[i] != i // 2 * 2 + 1:
                flag = False
                break
    if flag:
        print(2**(N//2) % p)
    else:
        print(0)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(len(a)-1):
    f = 0
    for j in range(i+1, len(a)):
        f += a[j]
        f = f%(10**9+7)
    x += a[i]*f
    x = x%(10**9+7)
print(x%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
m = sum(a)
for i in range(len(a)-1):
    m = (m-a[i])%(10**9+7)
    x += a[i]*m
    x = x%(10**9+7)
print(x%(10**9+7))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        q = collections.deque(map(int, input().split()))
        Q.append(q)

    games = N*(N-1)//2
    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(len(Q)):
            if len(Q[i]) == 0 or gamed[i] != 0:
                continue
            j = Q[i][0] - 1
            if len(Q[j]) != 0 and gamed[j] == 0:
                if Q[j][0] == i+1:
                    Q[i].popleft()
                    Q[j].popleft()
#                    print("game:", j+1, i+1, days)
                    b = True
                    gamed[i] = 1
                    gamed[j] = 1
                    games -= 1
                    continue
        days += 1
        if not b:
            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 ###

def f(n):
    a = 1
    for i in range(1, n+1):
        a *= i
    return a

def solve():
    (n,m) = map(int,input().split())
    if(abs(n-m)>1):
        return 0
    if(n==m):
        return (f(n) * f(m) * 2) % 1000000007
    return (f(n) * f(m)) % 1000000007

if(__name__ == "__main__"):
    print(solve())


### FIXED CODE ###

import math

mod = 1000000007

def solve():
    (n,m) = map(int,input().split())
    if(abs(n-m)>1):
        return 0
    if(n==m):
        return (math.factorial(n)**2 * 2) % mod
    if(n > m):
        return (math.factorial(m)**2 * n) % mod
    else:
        return (math.factorial(n)**2 * m) % mod

if(__name__ == "__main__"):
    print(solve())
### BUGGY CODE ###

import itertools
def aCb(a,b):return len(list(itertools.combinations([0]*a,b)))
n,a=int(input()),list(map(int,input().split()));b=[0]
for i in a:b.append(b[-1]+i)
b.sort();c=1;ans=0
for i in range(n):
  if b[i]==b[i+1]:c+=1
  else:
    if c>=2:ans+=aCb(c,2)
    c=1
if c>=2:ans+=aCb(c,2)
print(ans)

### FIXED CODE ###

n,a=int(input()),list(map(int,input().split()));b=[0]
for i in range(n):b.append(b[i]+a[i])
b.sort();c=1;ans=0
for i in range(n):
  if b[i]==b[i+1]:c+=1
  else:
    if c>=2:ans+=(c*(c-1))//2
    c=1
if c>=2:ans+=(c*(c-1))//2
print(ans)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(x) for x in input().split()]

ans = 10**9
for i in range(N):
    temp = []
    temp2 = []
    for j in range(N):
        if A[j] < A[i]:
            temp.append(temp2)
            temp2 = []
        else:
            temp2.append(A[j])
    temp.append(temp2)

    temp2 = temp
    temp = []
    for j in range(len(temp2)):
        temp += sorted(temp2[j])[:min(len(temp2[j]),max(0,len(temp2[j]) - K + 1))]
    temp = sorted(temp)

    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - A[i])
        
print(ans)
    


### FIXED CODE ###

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            if l >= K:
                temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    if l >= K:
        temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)