import itertools
import os
import sys
from collections import defaultdict
import numpy as np
if os.getenv("LOCAL"):
sys.stdin = open("_in.txt", "r")
sys.setrecursionlimit(2147483647)
INF = float("inf")
N, M = list(map(int, sys.stdin.readline().split()))
V, W = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
V = np.array(V)
W = np.array(W)
def knapsack_n():
if N <= 3:
masks = list(itertools.product([0, 1], repeat=N))
ws = W * masks
vs = V * masks
return vs[ws <= M].max()
assert N <= 30
# 2個に分けて組み合わせを全探索
half = N // 2
v1 = V[:half]
w1 = W[:half]
v2 = V[half:]
w2 = W[half:]
# 重さ全列挙
masks = np.array(np.meshgrid(*([[0, 1]] * len(v1)))).T.reshape(-1, len(v1)).T
w1 = np.dot(w1, masks)
v1 = np.dot(v1, masks)
# sort
idx = w1.argsort()
w1 = w1[idx]
# cummax
v1 = np.maximum.accumulate(v1[idx])
masks = np.array(np.meshgrid(*([[0, 1]] * len(v2)))).T.reshape(-1, len(v2)).T
w2 = np.dot(w2, masks)
v2 = np.dot(v2, masks)
ans = 0
for w, v in zip(w2, v2):
remains = M - w
if remains < 0:
continue
idx = np.searchsorted(w1, remains, side='right') - 1
ans = max(ans, v + v1[idx])
return ans
def knapsack_w():
# 重みに対して価値を最大化
# dp[w]: 価値が w となる最大の価値
dp = defaultdict(lambda: 0)
dp[W[0]] = V[0]
for i in range(1, N):
items = list(dp.items())
for w, v in items:
dp[w + W[i]] = max(dp[w + W[i]], v + V[i])
ret = 0
for w, v in dp.items():
if w <= M:
ret = max(ret, v)
return ret
def knapsack_v():
# 価値に対して重みを最小化
# dp[v]: 価値が v となる最小の重さ
dp = defaultdict(lambda: INF)
dp[V[0]] = W[0]
for i in range(1, N):
items = list(dp.items())
for v, w in items:
dp[v + V[i]] = min(dp[v + V[i]], w + W[i])
ret = 0
for v, w in dp.items():
if w <= M:
ret = max(ret, v)
return ret
if N <= 30:
print(knapsack_n())
elif W.max() <= 1000:
print(knapsack_w())
elif V.max() <= 1000:
print(knapsack_v())