CodeEff/ECCO huggingface dataset:
# Original solution
import sys
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    N, W = list(map(int, input().split()))
    w0, v0 = list(map(int, input().split()))
    item = [0, w0 * offset + v0]
    weight_sum, value_sum = w0, v0
    for _ in range(1, N):
        w, v = list(map(int, input().split()))
        item.append(w * offset + v)
        weight_sum += w
        value_sum += v

    if W < w0:
        print((0))
        return
    if weight_sum <= W:
        print(value_sum)
        return

    if w0 <= 3 * (N - 1):
        # dp[i][j] = (1~i番目の荷物を重さj以下で詰めたときの最大価値)
        dp = [[0] * (W + 1) for _ in range(N + 1)]
        for i in range(1, N + 1):
            w, v = item[i] // offset, item[i] % offset
            for j in range(w): dp[i][j] = dp[i - 1][j]
            for j in range(w, W + 1):
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        print((dp[N][W]))
        return

    # dp[i][j][k] = (1~i番目までのものを見たとき、重さが(j * w0 + k)以下で最大価値がいくらか)
    dp = [[[0] * (3 * (N - 1) + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = item[i] // offset, item[i] % offset
        for j in range(i + 1):
            for k in range(3 * (N - 1) + 1):
                weight = j * w0 + k
                q, r = (weight - w) // w0, (weight - w) % w0
                if weight < w:
                    dp[i][j][k] = dp[i - 1][j][k]
                elif (weight - w) % w0 > 3 * (N - 1):
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][3 * (N - 1)] + v)
                else:
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][q][r] + v)
    q, r = W // w0, min(W % w0, 3 * (N - 1))
    print((dp[N][q][r]))


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()
offset = 10**10

def main():
    """
    ナップサックで重さを飛び飛びにしてdpを軽くしなくても、
    そもそも重さが４パターンだから全探索で解けたのか。。。。。。
    """
    N, W = list(map(int, input().split()))
    item = [[] for _ in range(4)]
    length = [1, 0, 0, 0]
    w0, v0 = list(map(int, input().split()))
    item[0].append(v0)
    for _ in range(N - 1):
        w, v = list(map(int, input().split()))
        item[w - w0].append(v)
        length[w - w0] += 1
    for i in range(4): item[i].sort(reverse=True)

    # 重さの累積和
    S = []
    for i in range(4):
        S.append([0] + list(accumulate(item[i])))

    ans = 0
    for a in range(length[0] + 1):
        for b in range(length[1] + 1):
            for c in range(length[2] + 1):
                for d in range(length[3] + 1):
                    weight = a * w0 + b * (w0 + 1) + c * (w0 + 2) + d * (w0 + 3)
                    if weight > W: continue
                    ans = max(ans, S[0][a] + S[1][b] + S[2][c] + S[3][d])
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
def main():
    N, W = list(map(int, input().split()))
    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []
    i = 0
    while i < N:
        w, v = list(map(int, input().split()))
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                    if w <= W:
                        ans.append(v)

    print((max(ans)))

main()


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

    w1 = [0, 0]
    w2 = [0, 0]
    w3 = [0, 0]
    w4 = [0, 0]
    v1 = []
    v2 = []
    v3 = []
    v4 = []

    i = 0
    while i < N:
        w, v = list(map(int, input().split()))
        if i == 0 or w == w1[0]:
            w1[0] = w
            w1[1] += 1
            v1.append(v)
        elif w == w1[0] + 1:
            w2[0] = w
            w2[1] += 1
            v2.append(v)
        elif w == w1[0] + 2:
            w3[0] = w
            w3[1] += 1
            v3.append(v)
        elif w == w1[0] + 3:
            w4[0] = w
            w4[1] += 1
            v4.append(v)
        i += 1

    v1.sort(reverse=True)
    v2.sort(reverse=True)
    v3.sort(reverse=True)
    v4.sort(reverse=True)

    ans = []
    for i in range(w1[1] + 1):
        for j in range(w2[1] + 1):
            for k in range(w3[1] + 1):
                for l in range(w4[1] + 1):
                    w = w1[0] * i + w2[0] * j + w3[0] * k + w4[0] * l
                    if w <= W:
                        v = sum(v1[:i] + v2[:j] + v3[:k] + v4[:l])
                        ans.append(v)

    print((max(ans)))

main()
# Original solution
#060_D
n, w_ = list(map(int, input().split()))
w, v = [], []

for _ in range(n):
    a, b = list(map(int, input().split()))
    w.append(a)
    v.append(b)
    
dp = [[0 for _ in range(w_+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w_+1):
        if j < w[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])

print((dp[n][w_]))

# Optimized solution
#060_D
n, W = list(map(int, input().split()))
w1, w2, w3, w4 = [], [], [], []
w, v = list(map(int, input().split()))
w1.append(v)
for _ in range(n-1):
    a, b = list(map(int, input().split()))
    if a == w: w1.append(b)
    if a == w+1: w2.append(b)
    if a == w+2: w3.append(b)
    if a == w+3: w4.append(b)
    
for w_ in [w1, w2, w3, w4]:
    w_.sort(reverse= True)
    
ans = 0
for i in range(0, len(w1)+1):
    for j in range(0, len(w2)+1):
        for k in range(0, len(w3)+1):
            res = W - (i * w + j * (w+1) + k * (w+2))
            if res < 0:
                continue
            tmp = sum(w1[:i])+sum(w2[:j])+sum(w3[:k])+sum(w4[:res//(w+3)])
            ans = max(tmp, ans)
            
print(ans)
# Original solution
from itertools import accumulate
N,W = list(map(int,input().split()))

w0,v0 = list(map(int,input().split()))
W0,W1,W2,W3 = [],[],[],[]
W0.append(v0)
for i in range(1,N):
    w,v = list(map(int,input().split()))
    if w == w0:
        W0.append(v)
    elif w == w0+1:
        W1.append(v)
    elif w == w0+2:
        W2.append(v)
    else:
        W3.append(v)

W0.sort(reverse=True)
W1.sort(reverse=True)
W2.sort(reverse=True)
W3.sort(reverse=True)
V0 = [0]+list(accumulate(W0))
V1 = [0]+list(accumulate(W1))
V2 = [0]+list(accumulate(W2))
V3 = [0]+list(accumulate(W3))

Ans = 0
for i0 in range(len(V0)):
    for i1 in range(len(V1)):
        for i2 in range(len(V2)):
            for i3 in range(len(V3)):
                if w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    Ans = max(Ans,V0[i0]+V1[i1]+V2[i2]+V3[i3])

print(Ans)

# Optimized solution
from itertools import accumulate
N,W = list(map(int,input().split()))
V = [[] for _ in range(4)]
w0 = 0
for i in range(N):
    w,v = list(map(int,input().split()))
    if i==0:
        V[0].append(v)
        w0 = w
    else:
        V[w - w0].append(v)

# 降順ソート
for i in range(4):
    V[i].sort(reverse=True)

# 累積和
S = [[] for _ in range(4)]
for i in range(4):
    S[i] = [0] + list(accumulate(V[i]))

# 全探索
ans = 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 w0*i0 + (w0+1)*i1 + (w0+2)*i2 + (w0+3)*i3 <= W:
                    ans = max(ans, S[0][i0]+S[1][i1]+S[2][i2]+S[3][i3])

print(ans)
# Original solution

def solve(N, W, WVs):
    Ws = {}
    # print(N, ",", W, ",", WVs)
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in list(Ws.items()):
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        v1 = sum(Ws[wkeys[0]][:n1])
        if w1 > W:
            break
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            if w1 + w2 > W:
                break
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                if w1 + w2 + w3 > W:
                    break
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    if w1 + w2 + w3 + w4 > W:
                        break
                    m = max(m, v1 + v2 + v3 + v4)

    return m


if __name__ == "__main__":
    N, W = list(map(int, input().split(" ")))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print((solve(N, W, WVs)))


# Optimized solution
def solve(N, W, WVs):
    Ws = {}
    for w, v in WVs:
        Ws.setdefault(w, []).append(v)
    for w, v in list(Ws.items()):
        Ws[w] = sorted(v, key=lambda x: -x)
    wkeys = sorted(Ws.keys())

    m = 0
    for n1 in range(N + 1):
        w1 = n1 * wkeys[0]
        if w1 > W:
            break
        v1 = sum(Ws[wkeys[0]][:n1])
        for n2 in range(N - n1 + 1):
            if len(wkeys) >= 2:
                w2 = n2 * wkeys[1]
                if w1 + w2 > W:
                    break
                v2 = sum(Ws[wkeys[1]][:n2])
            else:
                w2, v2 = 0, 0
            for n3 in range(N - n1 - n2 + 1):
                if len(wkeys) >= 3:
                    w3 = n3 * wkeys[2]
                    if w1 + w2 + w3 > W:
                        break
                    v3 = sum(Ws[wkeys[2]][:n3])
                else:
                    w3, v3 = 0, 0
                for n4 in range(N - n1 - n2 - n3 + 1):
                    if len(wkeys) >= 4:
                        w4 = n4 * wkeys[3]
                        if w1 + w2 + w3 + w4 > W:
                            break
                        v4 = sum(Ws[wkeys[3]][:n4])
                    else:
                        w4, v4 = 0, 0

                    m = max(m, v1 + v2 + v3 + v4)

    return m

if __name__ == "__main__":
    N, W = list(map(int, input().split(" ")))
    WVs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print((solve(N, W, WVs)))
# Original solution
N, W = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]

w0 = items[0][0]
sizeX = min(W, sum([items[i][0] for i in range(N)])) // w0 + 1
sizeY = min(w0, 3 * (N - 1) + 1)
memo = [[[-1 for y in range(sizeY)] for x in range(sizeX)] for i in range(N + 1)]

memo[0][0][0] = 0
for i, (wi, vi) in enumerate(items):
    for x in range(sizeX):
        for y in range(sizeY):
            if memo[i][x][y] == -1: continue

            wn = w0 * x + y + wi
            if wn <= W:
                memo[i + 1][wn // w0][wn % w0] = memo[i][x][y] + vi

            memo[i + 1][x][y] = max(memo[i + 1][x][y], memo[i][x][y])

print((max(list(map(max, [memo[N][x] for x in range(sizeX)])))))


# Optimized solution
N, W = list(map(int, input().split()))
items = [tuple(map(int, input().split())) for i in range(N)]

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

memo[0] = {0: 0}
for i, (wi, vi) in enumerate(items):
    for w, v in list(memo[i].items()):

        if w + wi <= W:
            memo[i + 1][w + wi] = max(memo[i + 1].get(w + wi, 0), v + vi)

        memo[i + 1][w] = max(memo[i + 1].get(w, 0), v)

print((max(memo[N].values())))
# Original solution
N,W = list(map(int, input().split()))

knap = [0 for i in range(W+1)]
mono = []

for i in range(N):
    w,v = list(map(int, input().split()))
    mono.append([w,v])
mono.sort(key = lambda x:x[1], reverse=True)
for w, v in mono:
    for i in range(w, W+1)[::-1]:
        if knap[i] < knap[i-w] + v:
            knap[i] = knap[i-w] + v
print((knap[W]))


# Optimized solution
from itertools import accumulate
n,w=list(map(int, input().split()))
items = {}
for _ in range(n):
    u,v = list(map(int, input().split()))
    if u not in items:
        items[u] = []
    items[u].append(v)
cost = 0
acc = []
minkey = min(items.keys())
for i in range(4):
    if minkey + i in items:
        items[minkey + i].sort(reverse=True)
        acc.append([0] + list(accumulate(items[minkey + i])))
    else:
        acc.append([0])

ans = 0
for i in range(len(acc[0])):
    a = (i) * minkey
    if w < a:
        continue
    for j in range(len(acc[1])):
        b = (j) * (minkey+1)
        if w < a + b:
            continue
        for k in range(len(acc[2])):
            c = (k) * (minkey+2)
            if w < a + b + c:
                continue
            for l in range(len(acc[3])):
                d = (l) * (minkey+3)
                if w < a + b + c + d:
                    continue
                cost = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
                if cost > ans :
                    ans = cost

print(ans)
# Original solution
#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = list(map(int, input().split(" ")))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = list(map(int, input().split(" ")))
        if i == 0:
            w_list = list(range(w, w + 4))
        items[w].append(v)
        item_num[w] += 1

    for k in list(items.keys()):
        items[k].sort(reverse = True)

    cum = defaultdict(list)
    for k in list(items.keys()):
        sum_val = 0
        for e in items[k]:
            sum_val += e
            cum[k].append(sum_val)

    max_val = 0
    weights = list(items.keys())
    kinds = len(list(items.keys()))
    for element in itertools.product(list(range(N + 1)), repeat = kinds):
        w_sum = 0
        over_flag = False
        for i in range(kinds):
            if element[i] > item_num[weights[i]]:
                over_flag = True
                break
            w_sum += weights[i] * element[i]

        if w_sum > W or over_flag:
            continue

        val = 0
        for i in range(kinds):
            if element[i] >= 1:
                val += cum[weights[i]][element[i] - 1]
        if val > max_val:
            max_val = val

    print(max_val)


# Optimized solution
#coding:utf-8

N, W = list(map(int, input().split(" ")))
items = [tuple(map(int, input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print(search(0, 0))
# Original solution
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

N,W = list(map(int,(input().split())))
ww = []
vv = []

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

dp =  [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,N+1):
	weight = ww[i-1]
	value = vv[i-1]
	for j in range(W+1):
		if j >= weight:
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight]+value)
		else:
			dp[i][j] = dp[i-1][j]

print((dp[N][W]))

# Optimized solution
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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


w,v = list(map(int,(input().split())))
min_w = w
wv[0].append(v)

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

wv[0].sort(reverse=True)
wv[1].sort(reverse=True)
wv[2].sort(reverse=True)
wv[3].sort(reverse=True)
L1 = len(wv[0])
L2 = len(wv[1])
L3 = len(wv[2])
L4 = len(wv[3])

SUM = 0
sum_wv1 = [0]
for i in range(L1):
	SUM += wv[0][i]
	sum_wv1.append(SUM)

SUM = 0
sum_wv2 = [0]
for i in range(L2):
	SUM += wv[1][i]
	sum_wv2.append(SUM)

SUM = 0
sum_wv3 = [0]
for i in range(L3):
	SUM += wv[2][i]
	sum_wv3.append(SUM)

SUM = 0
sum_wv4 = [0]
for i in range(L4):
	SUM += wv[3][i]
	sum_wv4.append(SUM)

ans = 0

for n1 in range(L1+1):
	for n2 in range(L2+1):
		for n3 in range(L3+1):
			for n4 in range(L4+1):
				weight = min_w*(n1+n2+n3+n4) + n2 + 2*n3 + 3*n4
				if weight <= W:
					ans = max(ans,sum_wv1[n1]+sum_wv2[n2]+sum_wv3[n3]+sum_wv4[n4])

print(ans)
# Original solution
from sys import stdin
from itertools import accumulate
readline = stdin.readline

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

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0]) + 1):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1]) + 1):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2]) + 1):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = 0
            if i != 0:
              t += vs[0][i - 1]
            if j != 0:
              t += vs[1][j - 1]
            if k != 0:
              t += vs[2][k - 1]
            for l in range(len(vs[3]) + 1):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                if l == 0:
                    result = max(result, t)
                else:
                    result = max(result, t + vs[3][l -1])
print(result)


# Optimized solution
from sys import stdin
from itertools import accumulate
readline = stdin.readline

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

for i in range(4):
    vs[i].sort(reverse=True)
    vs[i] = [0] + list(accumulate(vs[i]))

result = 0
for i in range(len(vs[0])):
    a = W - w1 * i
    if a < 0:
        break
    for j in range(len(vs[1])):
        b = a - (w1 + 1) * j
        if b < 0:
            break
        for k in range(len(vs[2])):
            c = b - (w1 + 2) * k
            if c < 0:
                break
            t = vs[0][i] + vs[1][j] + vs[2][k]
            for l in range(len(vs[3])):
                d = c - (w1 + 3) * l
                if d < 0:
                    break
                result = max(result, t + vs[3][l])
print(result)
# Original solution
from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            value += sum(items[weights[i]][0:nums[i]])
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

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

for v in list(items.values()):
    v.sort(reverse=True)

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(W // w)
print((dfs([])))


# Optimized solution
from collections import defaultdict

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

MAX_NUM = []
len_weights = 0
def dfs(nums):
    if len(nums) == len_weights:
        sum_w = 0
        value = 0
        for i in range(len_weights):
            sum_w += weights[i] * nums[i]
            if nums[i] >= 1:
                value += items[weights[i]][nums[i] - 1]
        return value if sum_w <= W else 0
    value = 0
    i = len(nums)
    for j in range(MAX_NUM[i] + 1):
        value = max(value, dfs(nums + [j]))
    return value

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

for v in list(items.values()):
    v.sort(reverse=True)
    for i in range(1, len(v)):
        v[i] = v[i - 1] + v[i]

weights = sorted(items.keys())
len_weights = len(weights)
for w in weights:
    MAX_NUM.append(min(W // w, len(items[w])))
print((dfs([])))
# Original solution
from collections import defaultdict


def main():
    n, w = list(map(int, input().split()))
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    candidates = [0]
    for weight, value in sorted(DP.items()):
        if weight > w:
            break
        candidates.append(value)

    print((max(candidates)))


if __name__ == "__main__":
    main()


# Optimized solution
from collections import defaultdict


def main():
    n, w = list(map(int, input().split()))
    items = [list(map(int, input().split())) for _ in range(n)]
    DP = defaultdict(int)
    DP[0] = 0
    for weight, value in items:
        exists = list(DP.items())
        for key, total in exists:
            new_key = key + weight
            if new_key > w:
                continue
            new_total = total + value
            if DP[new_key] < new_total:
                DP[new_key] = new_total

    print((max(DP.values())))


if __name__ == "__main__":
    main()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

from collections import defaultdict
def resolve():
    n,W=list(map(int,input().split()))
    WV=[tuple(map(int,input().split())) for _ in range(n)]

    weight=set()
    for i in range(n+1):
        if(WV[0][0]*i>W): break
        for j in range(3*i+1):
            if(WV[0][0]*i+j>W): break
            weight.add(WV[0][0]*i+j)
    weight=sorted(weight)

    dp=defaultdict(int)
    for i in range(n):
        ndp=defaultdict(int)
        w,v=WV[i]
        for key in weight:
            ndp[key]=max(ndp[key],dp[key])
            if(key+w<=W): ndp[key+w]=max(ndp[key+w],dp[key]+v)
        dp=ndp

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

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,W=list(map(int,input().split()))
    w0,v=list(map(int,input().split()))
    V=[[] for _ in range(4)]
    V[0].append(v)
    for _ in range(n-1):
        w,v=list(map(int,input().split()))
        V[w-w0].append(v)
    for i in range(4):
        V[i].sort(reverse=1)
        for j in range(len(V[i])-1):
            V[i][j+1]+=V[i][j]
    for i in range(4):
        V[i].insert(0,0)

    ans=0
    from itertools import product
    for a,b,c,d in product(list(range(len(V[0]))),list(range(len(V[1]))),list(range(len(V[2]))),list(range(len(V[3])))):
        v=V[0][a]+V[1][b]+V[2][c]+V[3][d]
        if(a*w0+b*(w0+1)+c*(w0+2)+d*(w0+3)<=W): ans=max(ans,v)
    print(ans)
resolve()