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

s = input()
t = input()
ls = len( s)
lt = len( t)
ANS = [ [("", 0)]*(ls+1) for _ in range(lt+1) ]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            word, cnt = ANS[i-1][j-1]
            ANS[i][j] = ( word + s[j-1], cnt + 1)
        else:
            wordo, cnto = ANS[i-1][j]
            wordl, cntl = ANS[i][j-1]
            if cnto >= cntl:
                ANS[i][j] = (wordo, cnto)
            else:
                ANS[i][j] = (wordl, cntl)
print( ANS[lt][ls][0])


### FIXED CODE ###

s = input()
t = input()
ls = len( s)
lt = len( t)
CNT = [ [0]*(ls+1) for _ in range(lt+1)]
for i in range(1,lt+1):
    for j in range(1,ls+1):
        if s[j-1] == t[i-1]:
            CNT[i][j] = CNT[i-1][j-1]+1
        else:
            if CNT[i][j-1] >= CNT[i-1][j]:
                CNT[i][j] = CNT[i][j-1]
            else:
                CNT[i][j] = CNT[i-1][j]
i = lt
j = ls
ans = ""
while i > 0 and j > 0:
    if t[i-1] == s[j-1]:
        ans += t[i-1]
        i -= 1
        j -= 1
    else:
        if CNT[i-1][j] > CNT[i][j-1]:
            i -= 1
        else:
            j -= 1
print( ans[::-1])
### BUGGY CODE ###

n = int(input())
P = list(map(int,input().split()))
ans = 0
P = [float('inf')]+P
for i in range(1,n+1):
    if min(P[0:i]) >= P[i]:
        ans += 1
        #print(P[0:i])
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
tmpmin = l[0]
for i in range(n):
    if l[i] <= tmpmin:
        ans += 1
    tmpmin = min(tmpmin,l[i])
print(ans)
### BUGGY CODE ###

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

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

score = [0] * 2
l = 0
r = n - 1

for i in range(n-2):
    if A[l] + A[r - 1] > A[r] + A[l + 1]:
        score[i%2] += A[l]
        l += 1
    else:
        score[i%2] += A[r]
        r -= 1

score[n%2] += max(A[l], A[r])
score[(n+1)%2] += min(A[l], A[r])

if n % 2 == 0:
    print(score[0] - score[1])
else:
    print(DP[0][n-1])


### FIXED CODE ###

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

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

print(DP[0][n-1])
### BUGGY CODE ###

H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
Q = [list(map(int, input().split())) for _ in range(Q)]
# print(status)
for s, t in Q:
    ans = 0
    while s != t:
        tmp_t = s+D
        ans += abs((status[tmp_t][0] - status[s][0])) + abs(status[tmp_t][1]-status[s][1])
        s = tmp_t
    print(ans)


### FIXED CODE ###

# 累積話の考え方を使う
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
# print(status)

# 目的地は必ずDだけ小さいマスからしか移動してこない
cumulative_sum = [0] * (H*W+1)
for i in range(H*W+1):
    if i <= D:
        cumulative_sum[i] = 0
        continue
    else:
        cumulative_sum[i] = cumulative_sum[i-D] + abs(status[i][0] - status[i-D][0]) + abs(status[i][1] - status[i-D][1])

for s, t in query:
    print(cumulative_sum[t] - cumulative_sum[s])
### BUGGY CODE ###

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L, reverse=True)

    ans = 0
    for i in range(N):
        for j in range((i+1), N):
            if L[i]/2 >= L[j]:
                break 
            for k in range((j+1), N):
                if L[i] < (L[j]+L[k]):
                    ans += 1

    
    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    L = sorted(L)
    
    ans = 0
    for i in range(N-1):
        for j in range((i+1), N):    
            c = bisect.bisect_left(L, L[i] + L[j], j+1)
            ans += c - j - 1

    print(ans)


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

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)



### FIXED CODE ###

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
mul = 1

for i in range(N):
    x = S[i]
    for j in range(13):
        if x == '?':
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            n = int(x)
            dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + n) % 13] %= MOD


print(dp[N][5] % MOD)
### BUGGY CODE ###

n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  elif i<x and y-(y-x)//2+1<=j<=y:
    d=y-j+1+x-i
  elif x<=i<=x+(y-x)//2-1 and y<j:
    d=j-y+1+i-x
  elif x<=i and j<=y:
    d=min(j-i,i+y-x+1-j)
  elif i<x and y<j:
    d=j-y+1+x-i
  else:
    d=j-i
  return d
distmap=[]
for l in range(2,n+1):
  distmap[len(distmap):len(distmap)]=[dist(k,l) for k in range(1,l)]
[print(distmap.count(m)) for m in range(1,n)]

### FIXED CODE ###

n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  else:
    d=min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
  return d
distmap=[0]*n
for l in range(2,n+1):
  for k in range(1,l):
    distmap[dist(k,l)]+=1
print('\n'.join(map(str,distmap[1:])))
### BUGGY CODE ###

n=int(input())
list=input().split(" ")
x=1
for i in list:
  x*=int(i)
if x>1e18:
  print(-1)
else:
  print(x)

### FIXED CODE ###

import sys
n=int(input())
list=input().split(" ")
x=1

if "0" in list:
  print(0)
  sys.exit()
for i in list:
  x*=int(i)
  if x>1e18:
    print(-1)
    sys.exit()
print(x)
### BUGGY CODE ###

N, Q = map(int, input().split())
#graph = [[] for i in range(200010)]
#ans = [0 for i in range(200010)]
graph = [set() for i in range(N)]
ans = [0 for i in range(N)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)


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

    #graph[a].append(b)
    #graph[b].append(a)
    graph[a].add(b)
    graph[b].add(a)

for _ in range(Q):
    #p, x = map(int, input().split())
    p, x = [int(i) for i in input().split()]
    #p -= 1

    #ans[p] += x
    ans[p-1] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans)

### FIXED CODE ###

N, Q = map(int, input().split())
graph = [[] for i in range(200010)]
ans = [0 for i in range(200010)]
import sys
#sys.setrecursionlimit(100000)
sys.setrecursionlimit(10**7)
#
readline = sys.stdin.readline


for _ in range(N - 1):
    #a, b = map(int, input().split())
    a, b = map(int, readline().split())
    a -= 1
    b -= 1

    graph[a].append(b)
    graph[b].append(a)

for _ in range(Q):
    #p, x = map(int, input().split())
    p, x = map(int, readline().split())
    p -= 1

    ans[p] += x

def dfs(node, frm=-1):
    for to in graph[node]:
        if to == frm:
            continue
        ans[to] += ans[node]
        dfs(to, node)
dfs(0)

print(*ans[:N])
### BUGGY CODE ###

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

max_A = sorted(A)[-1]
second_A = sorted(A)[-2]
max_list = [i for i, x in enumerate(A) if x == max(A)]

if len(max_list) >= 2:
    for n in range(N):
        print(max_A)

else:
    for n in range(N):
        if A[n] != max(A):
            print(max(A))
        else:
            print(second_A)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

max_A = sorted(A)[-1]
second_A = sorted(A)[-2]

for n in range(N):
    if A[n] != max_A:
        print(max_A)
    else:
        print(second_A)
### BUGGY CODE ###

import re

S = 'S' + input()
new_s = list(S.replace('BC', 'D'))


cnt = 0
i = 1
while i < len(new_s):
    if new_s[i-1] == 'A' and  new_s[i] == 'D':
        cnt += 1
        new_s[i-1] = 'D'
        new_s[i] = 'A'
        i -= 2
    else:
        i += 1


print(cnt)

### FIXED CODE ###

import re

S = 'S' + input()
new_s = list(S.replace('BC', 'D'))


cnt = 0
A = 0
for i in range(len(new_s)):
    if new_s[i] == 'A':
        A += 1
    elif new_s[i] == 'D':
        cnt += A
    else:
        A = 0
print(cnt)
### BUGGY CODE ###


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

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

ans = [False] * N
able = [False] * (2*K+1)
able[0] = True
lis = [ [False] * N for i in range(2*K+1) ]

for i,na in enumerate(a):

    if na >= K:
        ans[i] = True
        continue

    nable = able.copy()

    for j in range(K):

        if able[j]:

            for nown in range(N):

                if not lis[j+na][nown] and lis[j][nown]:
                    lis[j + na][nown] = True

            lis[j+na][i] = True
            nable[j+na] = True

    able = nable

for i,na in enumerate(a):

    if na < K:

        for j in range(K,K+na,1):

            if lis[j][i]:
                ans[i] = True

#print (able)
r = N
for i in ans:
    if i:
        r -= 1

print (r)
        
    


### FIXED CODE ###


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

a = list(map(int,input().split()))
ans = N

q = 0

a.sort()
a.reverse()
nmax = 0

for i in range(N):

    q += 1
    
    if nmax + a[i] >= K:
        ans -= q
        q = 0

    else:
        nmax = nmax + a[i]

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

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

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
for i in set(a):
    c = a.count(i)
    b[i] += (c*(c-1)/2)
sumb = sum(b)
ans = []
for i in a:
    ans.append(int(sumb - (a.count(i)-1)))
print(*ans, sep='\n')

### FIXED CODE ###

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

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
count = 0
for i in range(n):
    b[a[i]] += 1
for i in range(n+1):
    count += b[i]*(b[i]-1)/2
for i in a:
    print(int(count-b[i]+1))
### BUGGY CODE ###

"""
最大公約数を最も落とす原因になっている整数を特定したい。
"""
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
count = Counter([])

for a in A:
    d = 1
    while d*d < a:
        if a%d == 0:
            if d not in count:
                count[d] = 0
            if a//d not in count:
                count[a//d] = 0
            count[d] += 1
            count[a//d] += 1
        d += 1
    if d**2 == a:
        if d not in count:
            count[d] = 0
        count[d] += 1

ans = 0
for k,v in count.items():
    if v >= N-1:
        ans = max(ans,k)
print(ans)


### FIXED CODE ###

"""
問題文を言い換えると、「最大公約数が最大になるように数字を一つ書き換えろ」ということ。
さらに言い換えると、「最大公約数が最大になるように数字を一つ消せ」ということ。
単純な線形探索でできるか？→NO

最大公約数を小さくする要因となっている数字を一つ消す。
どういう数字が最大公約数を小さくする要因になっているか？
他の数字と共通する素因数が少ない、小さい、次数が小さい。ただ、この3つを総合的に判断するのは難しすぎる。
素因数分解はやめて、単純に約数で探せばよいか。
各Aの約数を昇順で列挙しておく。
まずA1は必ず残すと仮定して、A1の約数の大きい方から順番に、ほかのAの約数になるかどうかを調べる。
その約数を含んでいないAが一つだけ存在するとき、そのAを消せば、その約数が最大公約数となる。

次に、A1を消す場合の最大公約数も求めて、A1を含める場合の最大公約数と比較して大きい方を採用する。
"""

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

#A1を必ず入れる場合の最大公約数を求める。
yakusu = []

a = A[0]
d = 1
while d*d < a:
    if a % d == 0:
        yakusu.append(d)
        yakusu.append(a//d)
    d += 1
if d*d == a:
    yakusu.append(d)
yakusu.sort(reverse=True)

ans = 1
for v in yakusu:
    cnt = 0
    for i in range(1,N):
        if A[i]%v != 0:
            cnt += 1
    if cnt <= 1:
        ans = v
        break

#A1を入れない場合の最大公約数を求める。
import math
g = A[1]
for i in range(2,N):
    g = math.gcd(g,A[i])

ans = max(ans,g)

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

A,B,Q=map(int,input().split())
s=[int(input()) for _ in range(A)]
t=[int(input()) for _ in range(B)]

#二分探索関数
def bin_search(x,seq):
    a=0
    b=len(seq)-1
    for i in range(len(seq)):
        center=((a+b)//2)
        if x>=seq[center]:
            a=center
        else:
            b=center
        if b-a<=1:
            break
    return seq[a],seq[b]

for i in range(Q):
    x=int(input())
    Nb_s0,Nb_s1=bin_search(x,s)
    Nb_t0,Nb_t1=bin_search(x,t)
    p1=abs(Nb_s0-x)
    p2=abs(Nb_s1-x)
    p3=abs(Nb_t0-x)
    p4=abs(Nb_t1-x)
    q1=abs(Nb_t0-Nb_s0)
    q2=abs(Nb_t0-Nb_s1)
    q3=abs(Nb_t1-Nb_s0)
    q4=abs(Nb_t1-Nb_s1)
    print(min(p1+q1,p2+q2,p1+q3,p2+q4,p3+q1,p4+q4,p3+q2,p4+q3))

### FIXED CODE ###

inf=10**11
A,B,Q=map(int,input().split())
s=[-inf]+[int(input()) for _ in range(A)]+[inf]
t=[-inf]+[int(input()) for _ in range(B)]+[inf]
x=[[i,int(input())] for i in range(Q)]

x.sort(key=lambda x:x[1])
i,s_i,t_i=0,0,0
ans=[]

for i in range(Q):
    while(1):
        if x[i][1]>=s[s_i]:
            s_i+=1
        else:
            break
    while(1):
        if x[i][1]>=t[t_i]:
            t_i+=1
        else:
            break
    ans.append([x[i][0],x[i][1],s[s_i-1],s[s_i],t[t_i-1],t[t_i]])
ans.sort(key=lambda x:x[0])
for i in range(Q):
    xx=ans[i][1]
    Nb_s0=ans[i][2]
    Nb_s1=ans[i][3]
    Nb_t0=ans[i][4]
    Nb_t1=ans[i][5]

    p1=abs(Nb_s0-xx)
    p2=abs(Nb_s1-xx)
    p3=abs(Nb_t0-xx)
    p4=abs(Nb_t1-xx)
    q1=abs(Nb_t0-Nb_s0)
    q2=abs(Nb_t0-Nb_s1)
    q3=abs(Nb_t1-Nb_s0)
    q4=abs(Nb_t1-Nb_s1)
    print(min(p1+q1,p2+q2,p1+q3,p2+q4,p3+q1,p4+q4,p3+q2,p4+q3))
### BUGGY CODE ###

from math import gcd

K = int(input())
res = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      s = gcd(a,b)
      res += gcd(s,c)

print(res)

### FIXED CODE ###

from math import gcd

K = int(input())
res = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      res += gcd(gcd(a,b),c)

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

from collections import deque
N=int(input())
K=list(input())

ans = 0
while len(K)>3:
    a = K.pop()
    for i, b in enumerate(K):
        if b != a:
            k = K[i+1:]
    
            for ii,c in enumerate(k):
                    if (c != b) and (c != a) and (ii != (len(k)-1)/2):
                        ans +=1
                 
print(ans)


### FIXED CODE ###

N=int(input())
K=input()
dic = {}
ts = 'RGB'
for t in ts:
    p=[]
    for ir, r in enumerate(K):
        if r == t:
            p.append(ir)
    dic[t] = p
ans1 = len(dic['R']) * len(dic['G']) * len(dic['B'])

ans2 = 0

for i in range(N):
    for j in range(i, N):
        if (i + 2*(j-i) < N):
            if  K[i] != K[j] and K[i] != K[i + 2*(j-i)] and K[i+2*(j-i)] != K[j]:
                ans2 +=1

print(ans1 - ans2)
### BUGGY CODE ###

from scipy.sparse import*
f=csgraph.johnson
n,m,l,*t=map(int,open(0).read().split())
m*=3
for i in f(f(csr_matrix((t[2:m:3],(t[:m:3],t[1:m:3])),[n+1]*2),0)<=l)[t[m+1::2],t[m+2::2]]:print(min(n,i)%n-1)

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

n = int(input())
ans = 1
arr = [int(x) for x in input().split()]
for each in arr:
    ans *= each
if (ans > 1e18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
ans = 1
arr = [int(x) for x in input().split()]
arr.sort()
for each in arr:
    ans *= each
    if (ans > 1e18):
        print(-1)
        exit(0)
print(ans)
### BUGGY CODE ###

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

Years = []
Ps = {}
for _ in range(M):
  P, Y = map(int, input().split())
  Years.append(Y)
  if P in Ps:
    Ps[P].append(Y)
  else:
    Ps[P] = [Y]

A = [0] * M
for i, v in Ps.items():
  for yi, y in enumerate(sorted(v)):
    index = Years.index(y)
    A[index] = str(i).zfill(6)+str(yi+1).zfill(6)
  
for a in A:
  print(a)

### FIXED CODE ###

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

dic = {i+1:[] for i in range(N)}

for i in range(M):
  p, y = map(int, input().split())
  dic[p].append((i,y))

for i in range(N):
  dic[i+1].sort(key=lambda x:x[1])
  
ans = [0] * M
for k, vs in dic.items():
  order = 1
  for c, y in vs:
    ans[c] = (k, order)
    order += 1

for city, order in ans:
  print(str(city).zfill(6)+str(order).zfill(6))
### BUGGY CODE ###

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    c = str(input())

    x = 1
    ans = 0
    y = 0

    for i in range(N):
        if y != 0:
            break
        if c[i] == "W":
            for j in range(x, N):
                ii = -j
                if c[ii] == "R" and j < N-i:
                    ans += 1
                    x = j+1
                    break
                if x>= N-i:
                    y += 1
                    break



    print(ans)

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    c = str(input())

    x = 1
    ans = 0
    y = 0

    for i in range(N):
        if y != 0:
            break
        if c[i] == "W":
            for j in range(x, N):
                ii = -j
                if c[ii] == "R" and j < N-i:
                    ans += 1
                    x = j+1
                    break
                if j>= N-i:
                    y += 1
                    break



    print(ans)

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

import sys 
sys.setrecursionlimit(2147483647)

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

def dfs(i,w):
    if (i,w) in dic: return dic[(i,w)]
    if i == N or w <=0: 
        dic[(i,w)] = 0
        return 0
    ma = 0 
    res1 = res2 = 0 
    if A[i][0] <=w:
        res1 = dfs(i + 1,w - A[i][0]) + A[i][1]
    res2 = dfs(i + 1,w)
    ma = max(res1,res2)
    dic[(i,w)] = ma
    return ma
dic = {}
res = dfs(0,W)
print(res)

### FIXED CODE ###

import sys 
sys.setrecursionlimit(2147483647)

N,W = map(int,input().split())
A = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for _ in range(W+1) ] for _ in range(N + 1)] 

for i in range(1,N + 1): 
    for j in range(W + 1): 
        if j - A[i-1][0] >= 0:
            res1 = dp[i - 1][j - A[i-1][0]] + A[i - 1][1]
            res2 = dp[i - 1][j]
            dp[i][j] = max(res1,res2)
        else:
            dp[i][j] = dp[i-1][j]
#print(dp)
print(max(dp[N]))
### BUGGY CODE ###

get_num=int(input())
get_list=[]

for i in range(get_num):
    tmp=input()
    if (tmp in get_list)==False:
        get_list.append(tmp)
    
print(len(get_list))

### FIXED CODE ###

get_num=int(input())
get_list=[]
count=0

for i in range(get_num):
    tmp=input()
    get_list.append(tmp)

list=list(set(get_list))
    
print(len(list))
### BUGGY CODE ###

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

value = abs(N - K)

if K == 1:
    print(0)
    exit()

while True:
    if abs(value - K) > abs(value):
        break
    value = abs(value - K)

print(value)

### FIXED CODE ###

N, K = map(int, input().split())
a = N // K
value = abs(N - a * K)
if K == 1:
    print(0)
    exit()
while True:
    if abs(value - K) > abs(value):
        break
    value = abs(value - K)
print(value)
### BUGGY CODE ###

import math

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

T = M * 1900 + (N-M) * 100

p = (1/2)**M
p2 = (1/2)**M
ans = 0
for i in range(1,5000000):
  ans += T * p2 * i
  p2 = p2 * (1-p)
  
print(math.ceil(ans))


### FIXED CODE ###

import math

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

T = M * 1900 + (N-M) * 100

p = (1/2)**M
p2 = (1/2)**M
ans = 0
for i in range(1,500000):
  ans += T * p2 * i
  p2 = p2 * (1-p)
  
print(round(ans))
### BUGGY CODE ###

N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = [[i] for i in range(N)]

def match(ab):
    a,b=ab
    lsa = friendlist[a].copy()
    lsb = friendlist[b].copy()
    if a in lsb:
        return
    else:
        for ip in lsa:
            friendlist[ip].extend(lsb)
        for ip in lsb:
            friendlist[ip].extend(lsa)

for i in range(M):
    match(matchlist[i])
print(max([len(item) for item in friendlist]))

### FIXED CODE ###

N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]

def getgroup(a):
    A = friendlist[a]
    if A == a:
        return a
    else:
        return getgroup(A)

def match(ab):
    A = getgroup(ab[0])
    B = getgroup(ab[1])
    if A==B:
        return
    elif len(gplist[A])<len(gplist[B]):
        gplist[B].extend(gplist[A])
        friendlist[A] = B
    else:
        gplist[A].extend(gplist[B])
        friendlist[B] = A

for i in range(M):
    # print(friendlist)
    # print(gplist)
    match(tuple(map(lambda x:int(x)-1,input().split())))

# print(friendlist)
# print(gplist)

print(max([len(item) for item in gplist]))