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

from collections import deque

n = int(input())

a = [[int(i) for i in input().split()] for j in range(n)]

check = [0]*n
used = [False]*n

d = deque()

for i in reversed(range(n)):
    if used[i] == True:
        continue
    if a[a[i][0]-1][0] == i+1:
        d.appendleft([i+1,a[i][0]])
        used[i] = True
        used[a[i][0]-1] = True
        check[i] = 1
        check[a[i][0]-1] = 1
        
ans = 0

if len(d) == 0:
    print(-1)
    exit()

#print(d)

while len(d) > 0:
    used = [False]*n
    ans += 1
    num = len(d)
    for i in range(num):
        tmp = d.popleft()
        for j in range(2):
            if check[tmp[j]-1] == n-1:
                continue
            psn = a[tmp[j]-1][check[tmp[j]-1]]-1
            mys = tmp[j]-1
            
            if check[mys] == n-1 or check[psn] == n:
                continue
            #print(tmp,psn,a[psn][check[psn]])
            #print(i,j,tmp,psn,check[mys],check[psn])
            if used[mys] == True or used[psn] == True:
                continue

            if a[psn][check[psn]] == mys+1:
                d.append([psn+1,mys+1])
                used[mys] = True
                used[psn] = True
                check[mys] += 1
                check[psn] += 1
    #print(d)

for i in range(n):
    if check[i] != n-1:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import time

from collections import deque

def main():
    t1 = time.time()

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [False]*n
    
    d = deque()
    
    for i in reversed(range(n)):
        if used[i] == True:
            continue
        if a[a[i][0]-1][0] == i+1:
            d.appendleft([i+1,a[i][0]])
            used[i] = True
            used[a[i][0]-1] = True
            check[i] = 1
            check[a[i][0]-1] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        exit()
    
    #print(d)
    
    while len(d) > 0:
        if time.time() - t1 >= 1.95:
            print(n*(n-1)//2)
            exit()
        used = [False]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                if check[tmp[j]-1] == n-1:
                    continue
                psn = a[tmp[j]-1][check[tmp[j]-1]]-1
                mys = tmp[j]-1
                
                if check[mys] == n-1 or check[psn] == n-1:
                    continue
                #print(tmp,psn,a[psn][check[psn]])
                #print(i,j,tmp,psn,check[mys],check[psn])
                if used[mys] == True or used[psn] == True:
                    continue
    
                if a[psn][check[psn]] == mys+1:
                    d.append([psn+1,mys+1])
                    used[mys] = True
                    used[psn] = True
                    check[mys] += 1
                    check[psn] += 1
        #print(d)
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            exit()
    
    print(ans)

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

S = input()
dp = [1] * len(S)
if len(S) % 2 == 0:
  c = len(S)
else:
  c = len(S) + 1
for i in range(c):
  nextdp = [0] * len(S)
  for j in range(len(S)):
    if S[j] == 'R':
      nextdp[j+1] += dp[j]
    else:
      nextdp[j-1] += dp[j]
  dp = nextdp
print(' '.join(map(str,dp)))

### FIXED CODE ###

S = input()
L = [0] * len(S)
count = 0
for i in range(len(S)):
  if S[i] == 'L':
    count += 1
    L[i] = count
  else:
    count = 0
count = 0
for i in range(len(S)-1,-1,-1):
  if S[i] == 'R':
    count += 1
    L[i] = count
  else:
    count = 0
ans = [0] * len(S)
for i in range(len(S)):
  if S[i] == 'R':
    if L[i] % 2 == 0:
      ans[i+L[i]] += 1
    else:
      ans[i+L[i]-1] += 1
  else:
    if L[i] % 2 == 0:
      ans[i-L[i]] += 1
    else:
      ans[i-L[i]+1] += 1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

lr = [list(map(int, input().split()))for _ in range(q)]

for l, r in lr:
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()

# 'AC'の累積和を求める
d = [0]*n
for i in range(1, n):
    d[i] += d[i-1]
    if s[i-1] == 'A' and s[i] == 'C':
        d[i] += 1
        
lr = [list(map(int, input().split())) for _ in range(q)]
for l, r in lr:
    print(d[r-1] - d[l-1])
### BUGGY CODE ###

n = int(input())
num_list = []
for _ in range(n):
    num_list.append(int(input()))

ans_list = []
for i in range(n):
    tmp = num_list.copy()
    tmp = tmp[:i] + tmp[i+1:]
    tmp.sort()
    maximum = tmp[-1]
    ans_list.append(maximum)

for j in ans_list:
    print(j)

### FIXED CODE ###

n = int(input())
num_list = []
for _ in range(n):
    num_list.append(int(input()))

copy =  num_list.copy()
copy.sort()
maximum = copy[-1]
second = copy[-2]

for i in num_list:
    if i == maximum:
        print(second)
    else:
        print(maximum)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
l = []
a = 0
for i in s:
  if i not in l:
    l.append(i)
    a += 1
    
print(a)


### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
print(len(set(s)))
### BUGGY CODE ###

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

A.sort()
B.sort()
C.sort()

def bin_search(vlist, targ):
    lb = -1
    ub = len(vlist)
    while ub - lb > 1:
        mid = (lb + ub) // 2
        if vlist[mid] >= targ:
            ub = mid
        else:
            lb = mid
    return ub

total = 0
for c in C:
    b_ub = bin_search(B, c)
    for b in B[:b_ub]:
        a_ub = bin_search(A, b)
        total += len(A[:a_ub])

print(total)

### FIXED CODE ###

import bisect
N = int(input())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    lower_a = bisect.bisect_left(A, b)
    upper_c = N - bisect.bisect_right(C, b)
    ans += lower_a*upper_c

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

#!/usr/bin/env python3
def main():
    (R, C, K), *D = [[*map(int,o.split())] for o in open(0)]
    D = {(r - 1, c - 1) : v for r, c, v in D}

    dp = [[[-1] * 4 for _ in [None] * C] for _ in [None] * R]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = D.get((r, c), None)
            for i in range(4):
                if dp[r][c][i] > -1:
                    if r < R - 1:
                        dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i])
                    if c < C - 1:
                        dp[r][c + 1][i] = max(dp[r][c + 1][i], dp[r][c][i])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[r + 1][c][0] = max(dp[r + 1][c][0], dp[r][c][i] + v)
                        if c < C - 1:
                            dp[r][c + 1][i + 1] = max(dp[r][c + 1][i + 1], dp[r][c][i] + v)

    v = D.get((R - 1, C - 1), 0)
    ans = dp[R - 1][C - 1][3]
    for i in range(3):
        ans = max(ans, dp[R - 1][C - 1][i] + v)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = map(int, input().split())
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    DP[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

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

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for left_d, right_d in itertools.permutations(dots, 2):
    if left_d[0] < right_d[0]:
        left_x = left_d[0]
        right_x = right_d[0]
    else:
        left_x = right_d[0]
        right_x =  left_d[0]
    
    for under_d, top_d in itertools.permutations(dots, 2):
        if under_d[1] < top_d[1]:
            under_y = under_d[1]
            top_y = top_d[1]
        else:
            under_y = top_d[1]
            top_y = under_d[1]
            
        counter = 0
        for d in dots:
            if  (left_x <= d[0]) and (d[0] <= right_x) and (under_y <= d[1]) and (d[1] <= top_y):
                counter += 1
            if counter >= K:
                break
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
            
print(ans)


### FIXED CODE ###

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

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

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def penalty(day, last, c):
    val = 0
    for i in range(26):
        val += c[i] * (day - last[i])
    return val

def calcScore(t, s, c):
    val = 0
    for i in range(26):
        last = 0
        for j in range(len(t)):
            if t[j] == i:
                val += s[j][i]
                val -= c[i]*(j-last)*(j-last-1)//2
                last = j
        val -= c[i]*(len(t)-last)*(len(t)-last-1)//2
    return val

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

score = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    t[d] = q-1
    ans[i] = calcScore(t, s, c)

for v in ans:
    print(v)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))
t = [-1]*(D+1)
for i in range(1, D+1):
    t[i] = int(input()) - 1
M = int(input())

scores = calcScore(t, s, c)

ans = [None]*M
for i in range(M):
    d, q = map(int, input().split())
    t[d] = q-1
    ans[i] = sum(calcScore(t, s, c))

for v in ans:
    print(v)
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

r, g, b, n = map(int, input().split())
ans = 0
for i in range(int(n/b)+1):
    for j in range(int(n/g)+1):
        for k in range(int(n/r)+1):
            cheak = r*k + g*j + b*i
            if cheak == n:
                ans += 1
            elif cheak > n:
                break
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

r, g, b, n = map(int, read().split())
cnt = 0
for i in range(n + 1):
    for j in range(n + 1):
        check = n - (r * i + g * j)
        if check >= 0:
            if check % b == 0:
                cnt += 1
        else:
            break
print(cnt)
### BUGGY CODE ###

S = input()
Q = int(input())
Query = list(input().split() for i in range(Q))
ans = S
for i in range(Q):
    if Query[i][0] == "1":
        ans = ans[::-1]
    if Query[i][0] == "2":
        if Query[i][1] == "1":
            ans = Query[i][2] + ans
        if Query[i][1] == "2":
            ans = ans + Query[i][2]
print(ans)

### FIXED CODE ###

from collections import deque
S = deque([input()])
Q = int(input())
Query = list(input().split() for i in range(Q))
sentou = 0
for i in range(Q):
    if Query[i][0] == "1":
        sentou += 1
    if Query[i][0] == "2":
        if Query[i][1] == "1":
            if sentou % 2:
                S.append(Query[i][2])
            else:
                S.appendleft(Query[i][2])
        if Query[i][1] == "2":
            if sentou % 2:
                S.appendleft(Query[i][2])
            else:
                S.append(Query[i][2])
ans = ""
for i in S:
    ans += i
if sentou % 2:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

from collections import deque
n,x,y = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
l[1].append(2)
for i in range(2,n):
    l[i].append(i+1)
    l[i].append(i-1)
l[n].append(n-1)
l[x].append(y)
l[y].append(x)
clist = [0]*(n+1)
#ここまでで、グラフが隣接リスト表記で表される
for k in range(1,n+1):
    d = deque()
    dist = [-1]*(n+1)
    dist[k] = 0
    d.append(k)
    while True:
        v = d.popleft()
        for i in l[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        if not d:
            break
    for j in dist[k+1:]:
        clist[j] += 1
for i in range(1,n):
    print(clist[i])

### FIXED CODE ###

n,x,y = [int(x) for x in input().split()]
count = [0]*(n+1)
for i in range(1,n):
    for j in range(i+1,n+1):
        if i < x and j <= x:
            nagasa = j - i
        elif i < x and x < j and j < y:
            nagasa = x-i + min(j-x,y-j+1)
        elif i < x and y <= j:
            nagasa = x-i + j - y + 1
        elif x <= i and i < y and j <= y:
            nagasa = min(j-i,i-x+y-j+1)
        elif x <= i and i < y and y < j:
            nagasa = j - y + min(y-i,i-x+1)
        elif y <= i:
            nagasa = j -i
        count[nagasa] += 1
for i in range(1,n):
    print(count[i])
### BUGGY CODE ###

N =int(input())
#S = list(map(str, input().split()))
# S = list(map(str, input().split()))
S = []
for _ in range(N):
    S.append(input())

#受け取った文字列をアルファベットに並び替え
S=[''.join(sorted(a)) for a in S]

#バケットを作って、出現回数をカウント
count=[0]*(len(set(S)))
unique_S=list(set(S))
ans=0
for ele in S:
    count[unique_S.index(ele)]+=1
count=sorted(count,reverse=True)

#階乗のコード
def cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact
#組み合わせのコード
def combination(n,c):
    a=(cor(n))/(cor(n-c)*cor(c))
    return a

for i in count:
    if i==1:
        break
    else:
        ans+=combination(i,2)
print(int(ans))

### FIXED CODE ###

from collections import Counter,defaultdict
N =int(input())
S = []
#キーが存在しなかったときのデフォルトの値を定義できる
dict=defaultdict(int)
ans=0
for _ in range(N):
    s=''.join(sorted(input()))
    ans+=dict[s]
    dict[s]+=1
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
a = [1]*n
b = [0]*n
for i in range(10**6):
  if a == b:
    break
  b = list(a)
  for _ in range(2):
    da = [0]*n
    for j in range(n):
      if s[j] == "R":
        da[j+1] += a[j]
      else:
        da[j-1] += a[j]
    a = list(da)
print(*a)

### FIXED CODE ###

s = input()
n = len(s)
rl = []
ll = []
c = 0
b = "R"
for i in range(n):
  if s[i] == b:
    c += 1
  else:
    if b == "R":
      rl.append(c)
      b = "L"
    else:
      ll.append(c)
      b = "R"
    c = 1
ll.append(c)
ans = []
for i,j in zip(rl,ll):
  ans += [0]*(i-1) + [i-i//2+j//2] + [i//2+j-j//2] + [0] *(j-1)
print(*ans)
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))

for i in range(n):#とばす番号
    ans = 0
    tmp = 0
    for j in range(n):
        if j == i:
            pass
        elif tmp*s[j] >= 0:#符号が同じとき
            if abs(s[j]) > abs(tmp):#外側へ移動
                ans += abs(tmp - s[j])
                tmp = s[j]
            elif abs(s[j]) < abs(tmp):#内側へ移動
                ans += abs(tmp - s[j])
                tmp = s[j]
        elif tmp*s[j] < 0:#符号が違う時
            ans += abs(tmp - s[j])
            tmp = s[j]
    ans += abs(tmp)
    print(ans)

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))

ans = 0
tmp = 0
for i in range(n):
    ans += abs(s[i] - tmp)
    tmp = s[i]
ans += abs(tmp)

s.insert(0,0)
s.insert(n+1,0)
for i in range(1,n+1):#とばす番号
    tmp_ans = ans
    a = s[i-1]
    tmp = s[i]
    b = s[i+1]
    if (b >= tmp and tmp >= a) or (b <= tmp and tmp <= a):
        pass
    else:
        if (a >= b and tmp > a) or (a <= b and tmp < a):
            tmp_ans -= abs(2*(tmp-a))
        else:
            tmp_ans -= abs(2*(tmp-b))
    print(tmp_ans)
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split()))[::-1] for _ in range(n)]
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
  cnt=0
  chk=[]
  for i in range(n-1):
    if i in chk:
      continue
    else:
      if a[i]:
        b=a[i][-1]-1
        if b in chk:
          continue
        else:
          if b>i and a[b][-1]-1==i:
            chk.append(a[i].pop()-1)
            chk.append(a[b].pop()-1)
            cnt+=1
  tcnt+=cnt
  ans+=1
  if cnt==0:
    ans=-1
    break
print(ans)

### FIXED CODE ###

from collections import deque
n=int(input())
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

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

def resolve():
    N = int(input())
    P_list = list(map(int, input().split()))
 
    answer = 0
 
    for i in range(1, len(P_list)+1):
        min_P_list_form_i = min(P_list[0:i])

        if P_list[i-1] <=min_P_list_form_i:
            answer += 1
 
    print(answer)
 
 
if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    p = input().split()
    num = 0
    mini = int(p[0])
    for i in range(N):
        if int(p[i])<=mini:
            num+=1
            mini=int(p[i])
    print(num)
 
 
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

for h in range(H):
    As = list(map(int, raw_input().split()))
    for w in range(W):
        Ah[As[w]-1] = h
        Aw[As[w]-1] = w

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    print(solve(L, R))
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
H,W,D = map(int, input().split())

# Ah = np.array([0]*(H*W))
# Aw = np.array([0]*(H*W))
A = [0]*(H*W)
for h in range(H):
    As = list(map(int, input().split()))
    for w in range(W):
        A[As[w]-1] = (h,w)
    # Aw[As-1] = np.arange(W)
    # Ah[As-1] = h


Q = int(input())

# def solve(l, r):
#     ans = 0
#     # ah = Ah[l-1:r][::D]
#     # ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
#     # aw = Aw[l-1:r][::D]
#     # ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
#     ans = sum(Ah[l-1:l+D][::D])
#     while l != r:
#         x,y = A[l-1]
#         x2,y2 = A[l+D-1]
#         ans += abs(x-x2) + abs(y-y2)
#         l += D
#     return ans

Ans = [0]*(H*W)
aa = (H*W) // D
bb = (H*W) % D
for dth in range(1,aa+1):
    for d in range(D):
        if dth*D+d >=H*W:
            break
        x,y = A[(dth-1)*D+d]
        x2,y2 = A[dth*D+d]
        ans = abs(x-x2) + abs(y-y2)
        Ans[dth*D+d] = Ans[(dth-1)*D+d] + ans



lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(Ans[R-1] - Ans[L-1])
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    dp = [0]*(W+1)

    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W,-1,-1):# 後ろから更新しないとダメ
            if j - w >= 0:
                dp[j] = max(dp[j], dp[j-w]+v)
    print(dp[W])    

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, W = map(int, input().split())
    w = [None] * N
    v = [None] * N

    for i in range(N):
        w[i], v[i] = map(int, input().split())
    
    dp = [[0]*(N+1) for _ in range(W+1)]
    for i in range(1,W+1):
        for j in range(N):
            if i - w[j] < 0:
                dp[i][j+1] = dp[i][j]
            else:
                dp[i][j+1] = max(dp[i][j], dp[i-w[j]][j]+v[j])
    print(dp[W][N])    

if __name__ == "__main__":
    main()