Harryxun/stf_run huggingface dataset:
from math import gcd

N,ma,mb=map(int,input().split())
med=[]
for i in range(0,N):
    a,b,c=map(int,input().split())
    med.append((a,b,c))

dp=[[[float("inf") for i in range(0,401)] for j in range(0,401)] for k in range(0,N)]
dp=[[float("inf") for i in range(0,401)] for j in range(0,401)]

for i in range(0,401):
    for j in range(0,401):
        if not (i==0 and j==0):
            g=gcd(i,j)
            I=i//g
            J=j//g
            if I==ma and J==mb:
                dp[i][j]=0
            else:
                g=gcd(i+med[0][0],j+med[0][1])
                I=(i+med[0][0])//g
                J=(j+med[0][1])//g
                if I==ma and J==mb:
                    dp[i][j]=med[0][2]

for i in range(1,N):
    a,b,c=med[i]
    for j in range(0,401-a):
        for k in range(0,401-b):
            dp[j][k]=min(dp[j][k],c+dp[j+a][k+b])

if dp[0][0]==float("inf"):
    print(-1)
else:
    print(dp[0][0])

### FIXED CODE ###

from fractions import gcd

N,ma,mb=map(int,input().split())
med=[]
for i in range(0,N):
    a,b,c=map(int,input().split())
    med.append((a,b,c))

dp=[[[float("inf") for i in range(0,401)] for j in range(0,401)] for k in range(0,N)]
dp=[[float("inf") for i in range(0,401)] for j in range(0,401)]

for i in range(0,401):
    for j in range(0,401):
        if not (i==0 and j==0):
            g=gcd(i,j)
            I=i//g
            J=j//g
            if I==ma and J==mb:
                dp[i][j]=0
            else:
                g=gcd(i+med[0][0],j+med[0][1])
                I=(i+med[0][0])//g
                J=(j+med[0][1])//g
                if I==ma and J==mb:
                    dp[i][j]=med[0][2]

for i in range(1,N):
    a,b,c=med[i]
    for j in range(0,401-a):
        for k in range(0,401-b):
            dp[j][k]=min(dp[j][k],c+dp[j+a][k+b])

if dp[0][0]==float("inf"):
    print(-1)
else:
    print(dp[0][0])
# A - Parking

N, A, B = map(int, raw_input().split)

print mint(N*A, B)

### FIXED CODE ###

# A - Parking

N, A, B = map(int, raw_input().split())

print min(N*A, B)
N,X= map(int,input().split())
List=list(map(int,input().split()))
a = 0
i = 0
while a < X:
    a = a + List[i]
    i = i + 1
print(i

### FIXED CODE ###

N,X= map(int,input().split())
List=list(map(int,input().split()))
List.append(0)
a = 0
i = 0
while a <= X and i <= N:
    a = a + List[i]
    i = i + 1
print(i)
for r in range(input()):
	if r > 0: print
	n = input()
	S = [[" "]*n for i in range(n)]
	x,y,dx,dy = 0,n-1,0,-1
	while 1:
		S[y][x] = "#"
		y += dy; x += dx
		try:
			if y+dy == -1: raise
			if S[y+dy][x+dx] == "#":
				y -= dy; x -= dx
				raise
		except:
			S[y][x] = "#"
			dx,dy = -dy,dx
			y += dy; x += dx
		if S[y+dy][x+dx] == "#" or S[y+dx][x-dy] == "#": break
	for i in range(n):
		print "".join(S[i])

### FIXED CODE ###

for r in range(input()):
	if r > 0: print
	n = input()
	if n < 3:
		for i in range(n): print "#"*(n-i) + " "*i
		continue
	S = [[" "]*n for i in range(n)]
	x,y,dx,dy = 0,n-1,0,-1
	while 1:
		S[y][x] = "#"
		y += dy; x += dx
		try:
			if S[y+dy][x+dx] == "#":
				if y+dy != -1:
					y -= dy; x -= dx
				raise
		except:
			S[y][x] = "#"
			dx,dy = -dy,dx
			y += dy; x += dx
		if S[y+dy][x+dx] == "#" or S[y+dx][x-dy] == "#": break
	for i in range(n):
		print "".join(S[i])
n = int(input())
s = input()
if n%2:
  print('No')
else:
  n /= 2
  if s[:n]==s[n:]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n = int(input())
s = input()
if n%2:
    print('No')
else:
    n //= 2
    if s[:n]==s[n:]:
        print('Yes')
    else:
        print('No')
def ans():
        n ,m = map(int, raw_input().split())
        A = list(map(int, raw_input().split()))
     
        divider = sum(A) / (4 * m + 1e-16)
     
        stack = 0
        for a in A:            
            if a >= divider:
                stack += 1
     
            if stack == m:
                return "Yes"
        return "No"        
     
     
    print ans()

### FIXED CODE ###

n ,m = map(int, raw_input().split())
A = sorted(list(map(int, raw_input().split())), reverse = True)
divider = sum(A) / (4.0 * m) 

stack = 0

for a in A:
    if a >= divider:
        stack += 1

if stack >= m:
    print 'Yes'
else:
    print 'No'
x,y = map(int,input().split())
import math
print(int((x * y) / math.gcd(x, y)))


### FIXED CODE ###

import fractions
x,y = map(int,input().split())
print(x*y//fractions.gcd(x,y))
INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  collections import deque

def main():
    s = list(input())
    k = int(input())
    for i in range(len(s)):
        if s[i] == 'a':
            continue
        if k >= ord('z') - ord(s[i]) + 1:
            k -= ord('z') - ord(s[i]) + 1
            s[i] = 'a'
            if k == 0:
                break
        else:
            i += 1
    
    if k > 0:
        s[-1] = chr(ord(s[-1]) + k)
    
    print(''.join(s))
if __name__ == '__main__':
    main()

### FIXED CODE ###

INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  collections import deque

def main():
    s = list(input())
    k = int(input())
    for i in range(len(s)):
        if s[i] == 'a':
            continue
        if k >= ord('z') - ord(s[i]) + 1:
            k -= ord('z') - ord(s[i]) + 1
            s[i] = 'a'
            if k == 0:
                break
    
    if k > 0:
        s[-1] = chr((ord(s[-1]) + k - 97)%26 + 97)
    
    print(''.join(s))
if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline
#'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
A = [int(input()) for _ in range(N)]
largest_num = 0
largest_ind = -1
second_large_num = 0

for i in range(N):
	if A[i] > largest_num:
		second_large_num = largest_num
		largest_num = A[i]
		largest_ind = i
	elif A[i] > second_large_num:
		second_large_num = A[i]
		
for i in range(N):
	if i == largest_ind:
		print(second_large_num)
	else:
		print(largest_num)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
A = [int(input()) for _ in range(N)]
largest_num = 0
largest_ind = -1
second_large_num = 0

for i in range(N):
	if A[i] > largest_num:
		second_large_num = largest_num
		largest_num = A[i]
		largest_ind = i
	elif A[i] > second_large_num:
		second_large_num = A[i]
		
for i in range(N):
	if i == largest_ind:
		print(second_large_num)
	else:
		print(largest_num)
import sys
input = sys.stdin.readline
import numpy as np
def print_ans(N, ar):
    """Test Case
    >>> print_ans(6,[["khabarovsk",-20, 1], ["moscow",-10, 2], ["kazan",-50, 3], ["kazan",-35, 4], ["moscow",-60, 5], ["khabarovsk",-40, 6]])
    3
    4
    6
    1
    5
    2
    >>> print_ans(10, [["yakutsk", -10, 1 ], ["yakutsk", -20, 2 ], ["yakutsk", -30, 3 ], ["yakutsk", -40, 4 ], ["yakutsk", -50, 5 ], ["yakutsk", -60, 6 ], ["yakutsk", -70, 7 ], ["yakutsk", -80, 8 ], ["yakutsk", -90, 9 ], ["yakutsk", -100,10]])
    10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    """
    ans = sorted(ar)
    for a in ans:
        print(a[2])

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = []
    for i in range(N):
        s, p = input().rstrip().split()
        n = int(n)
        ar.append([s, -n, i + 1])
    print_ans(N, ar)




### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
def print_ans(N, ar):
    """Test Case
    >>> print_ans(6,[["khabarovsk",-20, 1], ["moscow",-10, 2], ["kazan",-50, 3], ["kazan",-35, 4], ["moscow",-60, 5], ["khabarovsk",-40, 6]])
    3
    4
    6
    1
    5
    2
    >>> print_ans(10, [["yakutsk", -10, 1 ], ["yakutsk", -20, 2 ], ["yakutsk", -30, 3 ], ["yakutsk", -40, 4 ], ["yakutsk", -50, 5 ], ["yakutsk", -60, 6 ], ["yakutsk", -70, 7 ], ["yakutsk", -80, 8 ], ["yakutsk", -90, 9 ], ["yakutsk", -100,10]])
    10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    """
    ans = sorted(ar)
    for a in ans:
        print(a[2])

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = []
    for i in range(N):
        s, p = input().rstrip().split()
        p = int(p)
        ar.append([s, -p, i + 1])
    print_ans(N, ar)
A,B=map(int, input().split())
print(int(6-A-B))

### FIXED CODE ###

A=int(input())
B=int(input())
print((6-A-B))
n,x = map(int,input().split())
lis = list(map(int,input().split()))
d = 0
for i in range(n+1):
    d = d + lis[i]
    if d > x:
        print(i+1)
        break

### FIXED CODE ###

n,x = map(int,input().split())
lis = list(map(int,input().split()))
d = 0
c = 1
for l in lis:
    d += l
    if d <= x:
        c += 1
print(c)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    n = int(input().strip())
    a_list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

    print(a_list[n])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    n = int(input().strip())
    a_list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

    print(a_list[n - 1])


if __name__ == '__main__':
    main()
import numpy as np

def comb2(n):
    return int(n*(n-1)/2)

n = int(input())

a = np.array([int(i) for i in input().split()])

b = a+a.reshape(n,1)

e = np.ones(n, dtype=int) - np.identity(n, dtype=int)


c = b * e

for i in range(n):
    sums = 0
    tmp, counts = np.unique(c[i], return_counts=True)
    for num in counts:
        sums += comb2(num)
    print(sums)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
 
from collections import Counter
c=Counter(a)
 
max_c=0			# max combination
for i in c.values():
    max_c+=i*(i-1)//2     # 6+1+1 = 8
 
for num in a:
    k=c[num]      # 4 2 4 2 2 4 2 4
 
    print(max_c-(k*(k-1)//2)+((k-1)*(k-2)//2)) # different from max combination
                # 8 - 6 + 3
                # 5
import sys

def nextrec(coor,pt):
    if pt[2]==1:
        coor[0]=min(max(coor[0],pt[0]),coor[2])
    elif pt[2]==2:
        coor[2]=max(min(coor[2],pt[0]),coor[0])
    elif pt[2]==3:
        coor[1]=min(max(coor[1],pt[1]),coor[3])
    elif pt[2]==4:
        coor[3]=max(min(coor[3],pt[1]),coor[1])
def main(w,h,n,pts):
    rec=[0,0,w,h]
    for x in range(n):
        nextrec(rec,pt[x]):
    return (rec[0]-rec[2])*(rec[1]-rec[3])

w,h,n=map(int,sys.stdin.readline().strip().split())
pts=[list(map(int,sys.stdin.readline().strip().split())) \
    for x in range(n)]

print(main(w,h,n,pts))


### FIXED CODE ###

import sys

def nextrec(coor,pt):
    if pt[2]==1:
        coor[0]=min(max(coor[0],pt[0]),coor[2])
    elif pt[2]==2:
        coor[2]=max(min(coor[2],pt[0]),coor[0])
    elif pt[2]==3:
        coor[1]=min(max(coor[1],pt[1]),coor[3])
    elif pt[2]==4:
        coor[3]=max(min(coor[3],pt[1]),coor[1])
def main(w,h,n,pts):
    rec=[0,0,w,h]
    for x in range(n):
        nextrec(rec,pts[x])
    return (rec[0]-rec[2])*(rec[1]-rec[3])

w,h,n=map(int,sys.stdin.readline().strip().split())
pts=[list(map(int,sys.stdin.readline().strip().split())) \
    for x in range(n)]

print(main(w,h,n,pts))
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
alis = li()
for i in range(n):
    alis[i] //= 2

ima = alis[0] & -alis[0]
alis[0] //= (1<<(ima-1))
for i in range(1,n):
    tmp = alis[i] & -alis[i]
    if ima != tmp:
        print(0)
        exit()
    else:
        alis[i] //= (1<<(ima-1))

tmp = (1<<(ima-1))
#a>b
def gcd(a,b):
    if a < b:
        a,b = b,a
    while b!=0:
        a,b=b,a%b
    return a
#a>b
def lcm(a,b):
    return a*b // gcd(a,b)
ima = 1
for i in range(n):
    ima = lcm(alis[i],ima)
    if ima*tmp > m:
        print(0)
        exit()
ans = 0

tmm = m//ima
if tmm % 2 ==0:
    print(tmm//2)
else:
    print(tmm//2 +1)
    

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi() 
alis = li()
for i in range(n):
    alis[i] //= 2

ima = alis[0] & -alis[0]
alis[0] //= ima
for i in range(1,n):
    tmp = alis[i] & -alis[i]
    if ima != tmp:
        print(0)
        exit()
    else:
        alis[i] //=ima

tmp = ima
#a>b
def gcd(a,b):
    if a < b:
        a,b = b,a
    while b!=0:
        a,b=b,a%b
    return a
#a>b
def lcm(a,b):
    return a*b // gcd(a,b)
ima = 1
for i in range(n):
    ima = lcm(alis[i],ima)
    if ima*tmp > m:
        print(0)
        exit()
ans = 0

tmm = m//(ima*tmp)
if tmm % 2 ==0:
    print(tmm//2)
else:
    print(tmm//2 +1)
[a, b] = int(input()).split()
print(a*b, (a+b)*2)

### FIXED CODE ###

[a, b] = map(int, input().split())
print(a*b, (a+b)*2)
pi = 3.141592653589793
r = int(input())
print('{0:f} {1:f}'.format(r*r*pi, 2 * r * pi))

### FIXED CODE ###

pi = 3.141592653589793
r = float(input())
print('{0:f} {1:f}'.format(r*r*pi, 2 * r * pi))
X = int((input().split())[0])
Y = int((input().split())[1])
c = (4*X-Y)/2
t = (Y-2*X)/2
if c >= 0 and int(c) == c:
    if t >= 0 and int(t) == t:
        print("Yes")
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

XY = input().split()
X = int(XY[0])
Y = int(XY[1])
c = (4*X-Y)/2
t = (Y-2*X)/2
if c >= 0 and int(c) == c:
    if t >= 0 and int(t) == t:
        print("Yes")
    else:
        print("No")
else:
    print("No")
#スタック、キューを使う
from collections import deque

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

G = [ set() for row in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    G[A-1].add(B-1)
    G[B-1].add(A-1)

for i in range(N):
    G[i] = set(G[i])

#1グループに所属する最大数
ans = 0

#友達グループの数
count = 0

#各頂点の状態を色で表す WHITE:未訪問 GRAY:訪問中 BLACK:訪問完了
color = ['WHITE' for i in range(N)]

#訪問途中の頂点を退避しておくスタック
S = deque()

#次の要素を取り出す
def next(u):    
    #G[u]に格納されているまだ未訪問のノードを返す
    for i in range(len(G[u])):
        if color[G[u][i]] == 'WHITE':
            return G[u][i]
    return -1

def dfs(u):
    #始点uをスタックに追加
    S.append(u)
    color[u] = 'GRAY'
    global count
    count += 1
    #dequeは空のとき偽を返す
    while S:
        u = S[-1]    #スタックの頂点をuに格納
        v = next(u)
        #uに未訪問の隣接ノードがある
        if v != -1:
            color[v] = 'GRAY'
            count += 1
            S.append(v)
        else:
            S.pop()
            color[u]='BLACK'

#未訪問のuを始点として深さ優先探索
for i in range(N):
    count = 0
    if color[i] == 'WHITE':
        dfs(i)
        if count >= ans:
            ans = count

print(ans)


### FIXED CODE ###

"""
UnionFindにはいろいろな実装があるが, 本問ではparents配列にノード数を保持する実装だと非常に簡単に解ける. 
以下のようにしてノード数を保持する.
自身が子のとき, 親ノード番号を格納する.
自身が根のとき, ノード数を負の数で格納する.
つまり,　負の数のときは自身が根であり, その絶対値がその木のノード数を表す.
初期化時は、すべてのノードを−1で初期化する.
"""

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

#UnionFind木の実装
#-1で初期化し、併合のたびに-1していく
par = [-1] * N  #親
rank = [0] * N #木の深さ

#木の根を求める
def find(x):
    #par[x]が負のとき(自分が代表のとき)、自身を返す
    if par[x] < 0:
        return x
    else:
        return find(par[x])

#xとyの属する集合を併合
def unite(x,y):
    x = find(x)
    y = find(y)
    #もとから同じ集合のときは何もしない
    if (x == y):
        return
    #x側を常に小さくする
    if par[x] > par[y]:
            x, y = y, x
    
    #x側に併合する、その際xの代表にノード数を加算する
    par[x] += par[y]
    par[y] = x
    

#xとyが同じ集合に属するかどうか
def same(x,y):
    return find(x) == find(y)

for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    unite(x,y)


ans = min(par)

print(abs(ans))
# encoding: utf-8
import sys
sys.setrecursionlimit(10000)

H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

### FIXED CODE ###

# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)

DP = [[None] * W for i in range(H)]

def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    if DP[depth - 1][clm - 1] != None: return DP[depth - 1][clm - 1]
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        coeff = possible_route
        if clm > 1: coeff -= raw_route[clm - 1]
        if clm < W: coeff -= raw_route[clm]
        ans += coeff * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    if DP[depth - 1][clm - 1] == None: DP[depth - 1][clm - 1] = ans % (10 ** 9 + 7)
    return ans % (10 ** 9 + 7)

print(draw(1, 1))
s = input()
q = int(input())

for qi in range(q):
    command = input().split()

    a = int(command[1])
    b = int(command[2])
    if command[0] == 'print':
        print(s[a:b + 1])
    elif command[1] == 'reverse':
        s = s[:a] + reversed(s[a:b + 1]) + s[b + 1:]
    else:
        p = command[3]
        s = s[:a] + p + s[b+1:]

### FIXED CODE ###

s = input()
q = int(input())

for qi in range(q):
    command = input().split()

    a = int(command[1])
    b = int(command[2])
    
    if command[0] == 'print':
        print(s[a:b + 1])
        
    elif command[0] == 'reverse':
        s = s[:a] + s[a:b +1][::-1] + s[b + 1:]
        
    else:
        p = command[3]
        s = s[:a] + p + s[b+1:]
N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            # もらうDP
            if j-w >= 0:
                dp[i+1][n+1][j] = max(dp[i][n+1][j], dp[i][n][j-w]+v)
            else:
                dp[i+1][n+1][j] = dp[i][j+1][k]
            # if dp[i][n][j] == -1: continue
            # # if j + n*ws[0] > W: continue
            # # print("check",i,n,j,v)    )
            # dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # dp[i+1][n+1][j+w] = max(dp[i][n+1][j+w], dp[i][n][j] + v)
ans= 0
for i,As in enumerate(dp[N]):
    w = W - i*ws[0]
    if w > 0:
        ans = max(ans,max(As[:w+1]))
print(ans)   

### FIXED CODE ###

N,W = map(int, input().split())
ws = []
vs = []
for i in range(N):
    w,v = map(int, input().split())
    ws.append(w)
    vs.append(v)
ws_m = [w-ws[0] for w in ws]

"""
i番目まで見て、n個選んでいて、重さがwのときのvの最大値
ただし、wはN個選んだときにW-N*[w[0]]となっているので、そこをmaxとする
dp[i][n][w] 
"""
dp = [[[-1]*(3*N+10) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i,(w,v)  in enumerate(zip(ws_m,vs)):
    for n in range(i+1):
        for j in range(3*N):
            dp[i+1][n][j] = max(dp[i+1][n][j], dp[i][n][j])
            # if dp[i][n][j] == -1: continue
            if j + (n+1)*ws[0] + w <= W:
                dp[i+1][n+1][j+w] = max(dp[i][n][j+w], dp[i][n][j] + v)

ans= 0
for i,As in enumerate(dp[N]):
    w = min(W - i*ws[0], sum(ws_m))
    if w >= 0:
        ans = max(ans,max(As[:w+1]))
print(ans)
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(W) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #未訪問:0 訪問済み:1
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0
visit[(CH,CW)]=1

while q:
    kyori, fro_h, fro_w=q.popleft()
    visit[(fro_h, fro_w)]=1
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori < d[(to_h, to_w)]:
                visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori,to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and visit[(to_h, to_w)]==0:
            if kyori+1 < d[(to_h, to_w)]:
                #visit[(to_h, to_w)]=1
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1,to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]