CodeEff/ECCO huggingface dataset:
# Original solution
N, WW = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(N)]
W, V = list(zip(*l))
M = [{} for i in range(N + 1)]
def cal(i, w):
  if w in M[i]:
    return M[i][w]
  if i == N:
    v = 0
  elif w < W[i]:
    v = cal(i + 1, w)
  else:
    v = max(cal(i + 1, w), cal(i + 1, w - W[i]) + V[i])
  M[i][w] = v
  return v

print((cal(0, WW)))

# Optimized solution
N, W = list(map(int, input().split()))
d = {0:0}
for _ in range(N):
  w, v = list(map(int, input().split()))
  for dw, dv in list(d.copy().items()):
    if dw + w <= W:
      d[dw + w] = max(d.get(dw + w, 0), dv + v)
print((max(d.values())))
# Original solution
N,W=list(map(int,input().split()));d={0:0}
for _ in [0]*N:
 w,v=list(map(int,input().split()))
 for x,y in list(d.copy().items()):
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print((max(d.values())))

# Optimized solution
N,W,*A=list(map(int,open(0).read().split()));d={0:0}
for w,v in zip(A[::2],A[1::2]):
 for x,y in list(d.copy().items()):
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print((max(d.values())))
# Original solution
N,W,*A=list(map(int,open(0).read().split()));d={0:0}
for w,v in zip(A[::2],A[1::2]):
 for x,y in list(d.copy().items()):
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print((max(d.values())))

# Optimized solution
N,W,*A=list(map(int,open(0).read().split()));d={0:0}
while A:
 v,w=A.pop(),A.pop()
 for x,y in list(d.copy().items()):
  if x+w<=W:d[x+w]=max(d.get(x+w,0),y+v)
print((max(d.values())))
# Original solution
import sys
input = sys.stdin.readline

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

def knapsack(i, w) :
    if i == N :
        return 0
    
    M = knapsack(i + 1, w)
    
    if w >= wv[i][0] :
        M = max(M, knapsack(i + 1, w - wv[i][0]) + wv[i][1])
        
    return M
    
print((knapsack(0, W)))

# Optimized solution
import sys
input = sys.stdin.readline

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

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 0
for i0 in range(len(s[0])) :
    for i1 in range(len(s[1])) :
        for i2 in range(len(s[2])) :
            for i3 in range(len(s[3])) :
                if i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)
# Original solution
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc073/editorial.pdf
　　　https://ei1333.hateblo.jp/entry/2017/05/01/004235
　　　https://atcoder.jp/contests/abc060/submissions/3782609
・公式解
・累積和あり
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = list(map(int, input().split()))
wN = [0] * N
vN = [[] for i in range(4)]
for i in range(N):
    w, v = list(map(int, input().split()))
    if i == 0:
        offset = w
    vN[w-offset].append(v)

# 重さ毎のリストを降順ソート
for i in range(4):
    # 空リストのままだとこの後ループを回ってくれないので、[0]を追加する
    vN[i] = [0] + sorted(vN[i], reverse=True)

# 累積和
for i in range(4):
    for j in range(1, len(vN[i])):
        vN[i][j] = vN[i][j-1] + vN[i][j]

ans = 0
for i in range(len(vN[0])):
    for j in range(len(vN[1])):
        for k in range(len(vN[2])):
            for l in range(len(vN[3])):
                # 重さリミットを超えるパターンは対象外
                if offset * i + (offset+1) * j + (offset+2) * k + (offset+3) * l > W:
                    continue
                ans = max(vN[0][i] + vN[1][j] + vN[2][k] + vN[3][l], ans)
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

"""
参考：https://atcoder.jp/contests/abc060/submissions/3958560
・前から普通にDPもdictでやってみる。
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import defaultdict

N, W = list(map(int, input().split()))
wN = [0] * N
vN = [0] * N
for i in range(N):
    wN[i], vN[i] = list(map(int, input().split()))

# 重さの添字にはdictを使う
dp = [defaultdict(int) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for k, v in list(dp[i].items()):
        # 重さの条件がOKなら、今回の値を足したケースを次のステップに送る
        if k + wN[i] <= W:
            dp[i+1][k+wN[i]] = max(dp[i][k] + vN[i], dp[i+1][k+wN[i]])
        # 足さないケースを送る
        dp[i+1][k] = max(dp[i][k], dp[i+1][k])

# 最適が重さWを全て使った場合とは限らないのでNステップ目のmaxを取る
print((max(dp[N].values())))
# Original solution
import sys
from collections import defaultdict, deque

def main():
    input = sys.stdin.readline
    N, W = list(map(int, input().split()))
    A = [tuple(map(int, input().split())) for _ in range(N)]

    d = defaultdict(lambda: 0)
    q = deque()
    for a in A:
        while len(q) > 0:
            w0, v0 = q.popleft()

            w1 = w0 + a[0]
            v1 = v0 + a[1]

            if w1 <= W:
                d[w1] = max(d[w1], v1)

            d[w0] = max(d[w0], v0)

        if a[0] <= W:
            q.append(a)

        for key in list(d.keys()):
            q.append((key, d[key]))

    ans = 0
    for key in list(d.keys()):
        ans = max(ans, d[key])

    return ans


if __name__ == '__main__':
    print((main()))


# Optimized solution
# Editorial

import sys
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N, W = list(map(int, input().split()))

    V = [[] for _ in range(4)]
    w0, v0 = list(map(int, input().split()))
    V[0].append(v0)
    for _ in range(N-1):
        w, v = list(map(int, input().split()))
        V[w-w0].append(v)

    for i in range(4):
        V[i] = list(accumulate([0] + sorted(V[i], key=lambda x: -x)))

    ans = 0
    for i in range(len(V[0])):
        for j in range(len(V[1])):
            for k in range(len(V[2])):
                weight = w0 * i + (w0 + 1) * j + (w0 + 2) * k
                if weight <= W:
                    l  = min(len(V[3]) - 1, (W - weight) // (w0 + 3))
                    ans = max(ans, V[0][i] + V[1][j] + V[2][k] + V[3][l])

    return ans


if __name__ == '__main__':
    print((main()))
# Original solution
from collections import defaultdict
N,W=list(map(int,input().split()))

a=defaultdict(lambda:[])
for i in range(N):
	w,v=list(map(int,input().split()))
	a[w]=a[w]+[v]

for i,j in list(a.items()):
	a[i]=sorted(j,reverse=True)



lst=[]
for i,j in list(a.items()):
	lst.append( (i,len(j)) )

max_val=0
if len(lst)==1:
	w1=lst[0][0]
	c1=lst[0][1]
	for i in range(c1+1):
		if i*w1<=W:
			max_val=max(max_val, sum(a[w1][:i]))

elif len(lst)==2:
	w1=lst[0][0]; w2=lst[1][0]
	c1=lst[0][1]; c2=lst[1][1]
	for i in range(c1+1):
		for j in range(c2+1):
				if i*w1+j*w2<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j]))

elif len(lst)==3:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				if i*w1+j*w2+k*w3<=W:
					max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k]))

elif len(lst)==4:
	w1=lst[0][0]; w2=lst[1][0]; w3=lst[2][0]; w4=lst[3][0]
	c1=lst[0][1]; c2=lst[1][1]; c3=lst[2][1]; c4=lst[3][1]
	for i in range(c1+1):
		for j in range(c2+1):
			for k in range(c3+1):
				for m in range(c4+1):
					if i*w1+j*w2+k*w3+m*w4<=W:
						max_val=max(max_val, sum(a[w1][:i])+sum(a[w2][:j])+sum(a[w3][:k])+sum(a[w4][:m]))

print(max_val)



# Optimized solution
from collections import defaultdict
N,W=list(map(int,input().split()))
wv=[]

for i in range(N):
	w,v=list(map(int,input().split()))
	wv.append((w,v))


dp=defaultdict(lambda: 0)	# Weight:Value
dp[0]=0

for w1,v1 in wv:
	d=dp.copy()
	for w,v in list(dp.items()):
		dp[w+w1]=max( dp[w+w1], d[w]+v1 )


l1=[x for x in list(dp.items()) if x[0]<=W]
print(sorted(l1, key=lambda x: x[1],reverse=True)[0][1])
# Original solution
N, W = list(map(int, input().split()))
data = tuple(tuple(map(int, input().split())) for _ in range(N))
table = [dict() for _ in range(N + 1)]
table[0][0] = 0
for n in range(N):
    weight, value = data[n]
    for w, now in list(table[n].items()):
        table[n + 1][w] = max(table[n + 1].get(w, 0), now)
        if w + weight <= W:
            table[n + 1][w + weight] = max(table[n + 1].get(w + weight, 0), now + value)
print((max(table[N].values())))

# Optimized solution
N, W = list(map(int, input().split()))
data = tuple(tuple(map(int, input().split())) for _ in range(N))
d = {0: 0}
for n in range(N):
    weight, value = data[n]
    for w, now in list(d.copy().items()):
        if w + weight <= W:
            d[w + weight] = max(d.get(w + weight, 0), now + value)
print((max(d.values())))
# Original solution
#入力
n, W=list(map(int, input().split()))
w,v=[],[]
for i in range(n):
  a,b=list(map(int,input().split()))
  w.append(a)
  v.append(b)

# i番目以降から重さの総和がj 以下になるように選んだ時の重量
def rec(i,j):
  #既に計算されているなら、メモdp[][]を受け取る
  if dp[i][j]>=0:
    return dp[i][j]
  if i==n:#もう品物がないから終わり
    res=0
  elif w[i]>j:#i番目の荷物は入らないから次へ
    res= rec(i+1,j)
  else:#i番目の荷物が入る場合と入らない場合の両方を試す
    res=max(rec(i+1,j), rec(i+1,j-w[i]) +v[i])
  dp[i][j]=res
  return res

dp=[[-1 for i in range(W+1)] for j in range(n+1)]#メモの初期化
print((rec(0,W)))

# Optimized solution
N, W = list(map(int, input().split()))

value_table = [[] for i in range(4)]
for i in range(N):
    w, v = list(map(int,input().split()))
    if i == 0:
        w1 = w
    value_table[w-w1] += [v]

[value_table[i].sort(reverse=True) for i in range(4)]

ans = 0
value_table_ruiseki = [[0] for i in range(4)]
for i in range(4):
    for v in value_table[i]:
        value_table_ruiseki[i] += [value_table_ruiseki[i][-1] + v]

ans = 0
for i, iv in enumerate(value_table_ruiseki[0]):
    for j, jv in enumerate(value_table_ruiseki[1]):
        for k, kv in enumerate(value_table_ruiseki[2]):
            for ell, ellv in enumerate(value_table_ruiseki[3]):
                weight = i*w1 + j*(w1+1) + k*(w1+2) + ell*(w1+3)
                value = iv + jv + kv + ellv
                if weight <=W:
                    ans = max(ans, value)

print(ans)
# Original solution
N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
def toru(a,b,c,d,nw):
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a+1,b,c,d+1,nw+w0+3)+v[3][d]
    return max


maxv=toru(0,0,0,0,0)

print(maxv)


# Optimized solution
N,W=list(map(int,input().split()))
v=[[],[],[],[]]
kosu=[0,0,0,0]
kr=list(map(int,input().split()))
v[0].append(kr[1])
w0=kr[0]
for i in range(1,N):
    kr=list(map(int,input().split()))
    v[kr[0]-w0].append(kr[1])
for i in range(4):
    v[i].sort()
    v[i].reverse()
kos=[len(v[0]),len(v[1]),len(v[2]),len(v[3])]
kk=[-1]*((kos[0]+1)*(kos[1]+1)*(kos[2]+1)*(kos[3]+1))
def toru(a,b,c,d,nw):
    global kk
    if kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]!=-1:
        return kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]
    max=0
    if a<kos[0] and W>=nw+w0 and max<toru(a+1,b,c,d,nw+w0)+v[0][a]:
        max=toru(a+1,b,c,d,nw+w0)+v[0][a]
    if b<kos[1] and W>=nw+w0+1 and max<toru(a,b+1,c,d,nw+w0+1)+v[1][b]:
        max=toru(a,b+1,c,d,nw+w0+1)+v[1][b]
    if c<kos[2] and W>=nw+w0+2 and max<toru(a,b,c+1,d,nw+w0+2)+v[2][c]:
        max=toru(a,b,c+1,d,nw+w0+2)+v[2][c]
    if d<kos[3] and W>=nw+w0+3 and max<toru(a,b,c,d+1,nw+w0+3)+v[3][d]:
        max=toru(a,b,c,d+1,nw+w0+3)+v[3][d]
    kk[a+(kos[0]+1)*(b+((kos[1]+1)*(c+(kos[2]+1)*d)))]=max
    return max
 
 
maxv=toru(0,0,0,0,0)
 
print(maxv)
# Original solution
n,W = list(map(int,input().split()))
w = [0]*n
v = [0]*n
for i in range(n): w[i],v[i] = list(map(int,input().split()))
x = w[0]
for i in range(n): w[i] -= x
dp = [[[0]*(4*n+1) for _ in range(n+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(i+1):
        for k in range(4*n+1):
            if (j+1)*x+k <= W and k-w[i] >= 0:
                dp[i+1][j+1][k] = max(dp[i+1][j+1][k],dp[i][j][k-w[i]]+v[i])
            dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k])

"""
for i in range(n+1):
    print(i,"///////////////////////////////////////////////")
    for j in range(n+1):
        print(dp[i][j])
"""
print((max(max(dp[n][j]) for j in range(n+1))))

# Optimized solution
n,W = list(map(int,input().split()))
lst = [[0]*(n+1) for _ in range(4)]
for i in range(n):
    w,v = list(map(int,input().split()))
    if i == 0: x = w
    lst[w-x].append(v)
for i in range(4):
    lst[i].sort(reverse=True)
    for j in range(n): lst[i][j+1] += lst[i][j]
ans = 0
for a in range(n+1):
    for b in range(n+1-a):
        for c in range(n+1-a-b):
            if x*a+(x+1)*b+(x+2)*c > W: continue
            d = max((W-x*a-(x+1)*b-(x+2)*c)//(x+3),0)
            sumv = 0
            for i,j in enumerate((a,b,c,d)):
                if j == 0: continue
                sumv += lst[i][j-1]
            ans = max(sumv,ans)
print(ans)
# Original solution

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

weights = []
values = []
for i in range(N):
    lst = [int(e) for e in input().split()]
    weights.append(lst[0])
    values.append(lst[1])

#df = np.array(ary)

def rec(i, j):
    if i == N:
        return 0
    elif j < weights[i]:
        return rec(i+1, j)
    else:
        return max(rec(i+1, j), rec(i+1, j-weights[i]) + values[i])

print((rec(0, W)))

# Optimized solution

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

weights = []
values = []
for i in range(N):
    lst = [int(e) for e in input().split()]
    weights.append(lst[0])
    values.append(lst[1])


dp = [{} for j in range(N+1)]

def rec(i, j):
    if j in dp[i]:
        return dp[i][j]

    res = 0
    if i == N:
        res = 0
    elif j < weights[i]:
        res = rec(i+1, j)
    else:
        res = max(
            rec(i+1, j),
            rec(i+1, j-weights[i]) + values[i]
        )

    dp[i][j] = res
    return res


print((rec(0, W)))
# Original solution
from collections import *
N,W = list(map(int,input().split()))
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w,v = list(map(int,input().split()))
  for k,b in list(dp.copy().items()):
    if k+w<=W:
      dp[k+w] = max(dp[k+w],b+v)

print((max(dp.values())))

# Optimized solution
from collections import *
N,W = list(map(int,input().split()))
dp = defaultdict(int)
dp[0] = 0

for n in range(N):
  w1,v1 = list(map(int,input().split()))
  for w2,v2 in list(dp.copy().items()):
    if w1+w2<=W:
      dp[w1+w2] = max(dp[w1+w2],v1+v2)

print((max(dp.values())))
# Original solution
from collections import defaultdict
n, W = list(map(int, input().split()))
dd = defaultdict(list)
for i in range(n):
    weight, value = list(map(int, input().split()))
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            for z in range(len(dd[d])+1):
                if W < a*w+b*x+c*y+d*z:
                    continue
                val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
                ans = max(ans, val)
print(ans)


# Optimized solution
from collections import defaultdict
n, W = list(map(int, input().split()))
dd = defaultdict(list)
for i in range(n):
    weight, value = list(map(int, input().split()))
    dd[weight].append(value)

a = min(dd.keys())
b, c, d = a+1, a+2, a+3
Vcum = defaultdict(lambda: [0])
for k in [a, b, c, d]:
    s = 0
    dd[k].sort(reverse=True)
    for val in dd[k]:
        s += val
        Vcum[k].append(s)

ans = 0
for w in range(len(dd[a])+1):
    for x in range(len(dd[b])+1):
        for y in range(len(dd[c])+1):
            if W < a*w+b*x+c*y:
                break
            z = min((W-a*w-b*x-c*y)//d, len(dd[d]))
            val = Vcum[a][w]+Vcum[b][x]+Vcum[c][y]+Vcum[d][z]
            ans = max(ans, val)
print(ans)
# Original solution
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = min(W - w1 * j, 3 * n)
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)


# Optimized solution
from itertools import accumulate

n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

for i in range(4):
    weights[i].sort(reverse=True)

acc = [[0] + list(accumulate(li)) for li in weights]

ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            for l, e4 in enumerate(acc[3]):
                if w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l <= W:
                    ans = max(ans, e1 + e2 + e3 + e4)

print(ans)
# Original solution
from itertools import accumulate

n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

for i in range(4):
    weights[i].sort(reverse=True)

acc = [[0] + list(accumulate(li)) for li in weights]

ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            for l, e4 in enumerate(acc[3]):
                if w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l <= W:
                    ans = max(ans, e1 + e2 + e3 + e4)

print(ans)


# Optimized solution
from itertools import accumulate

n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]

w1 = wv[0][0]
weights = [[] for _ in range(4)]

for w, v in wv:
    w_diff = w - w1
    weights[w_diff].append(v)

for i in range(4):
    weights[i].sort(reverse=True)

acc = [[0] + list(accumulate(li)) for li in weights]

l3 = len(weights[3])
ans = 0
for i, e1 in enumerate(acc[0]):
    for j, e2 in enumerate(acc[1]):
        for k, e3 in enumerate(acc[2]):
            w_sm = w1 * i + (w1 + 1) * j + (w1 + 2) * k
            if w_sm > W:
                break

            l = min((W - w_sm) // (w1 + 3), l3)
            val = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
            ans = max(ans, val)

print(ans)
# Original solution
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for i in range(N)]
w1 = wv[0][0]

w_to_idx = {0:0}
idx_to_w = {0:0}
idx_W = 0
def calc():
  global w_to_idx, idx_to_w, idx_W
  idx = 1
  w_max = 0
  for i in range(1, N+1):
    w = w1*i
    for j in range(3*i + 1):
      ww = w + j
      if ww in w_to_idx:
        continue
      w_to_idx[ww] = idx
      idx_to_w[idx] = ww
      if w_max < ww <= W:
        w_max = ww
        idx_W = idx
      idx += 1

calc()
n = len(w_to_idx)
dp = [[0]*n for i in range(N+1)]
for i, (w, v) in enumerate(wv, 1):
  for j in range(n):
    dp[i][j] = dp[i-1][j]
    ww = idx_to_w[j]
    if ww >= w and ww-w in w_to_idx:
      jj = w_to_idx[ww - w]
      dp[i][j] = max(dp[i][j], dp[i-1][jj] + v)

print((max(dp[-1][:idx_W+1])))

# Optimized solution
from itertools import accumulate

N, W = list(map(int, input().split()))
wv = {}
w1 = 0
for i in range(N):
  w, v = list(map(int, input().split()))
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)
# Original solution
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        tmp = defaultdict(int)  # 価値の最大値を更新できた荷物の重さの情報
        for kw, kv in list(dp.items()):
            if kw + w <= W:
                if kw + w in dp:
                    tmp[kw + w] = max(dp[kw + w], kv + v)
                else:
                    tmp[kw + w] = kv + v
        for key, value in list(tmp.items()):
            dp[key] = value
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print((d_simple_knapsack(N, W, Baggage)))

# Optimized solution
def d_simple_knapsack(N, W, Baggage):
    from collections import defaultdict
    # dp[w]:ナップサックに重さがwになるように荷物を入れたときの価値の最大値
    dp = defaultdict(int)
    dp[0] = 0  # 重さ0で達成できる価値は0とする
    for w, v in Baggage:
        # dpの各要素(現時点におけるナップサック内の荷物の重さ)に対して、
        # 注目した荷物を入れても重さがWを超えなければ、
        # ナップサックに荷物を入れて価値の最大値を更新する
        latest_dp = list(dp.items())
        for kw, kv in latest_dp:
            if kw + w <= W:
                dp[kw + w] = max(dp[kw + w], kv + v)
    ans = max(dp.values())
    return ans

N, W = [int(i) for i in input().split()]
Baggage = [[int(i) for i in input().split()] for j in range(N)]
print((d_simple_knapsack(N, W, Baggage)))