import bisect
INF = 10**10
n, W = map(int, input().split())
w = []
v = []
max_w = 0
max_v = 0
for i in range(n):
v_, w_ = map(int, input().split())
if max_v < v_:
max_v = v_
if max_w < w_:
max_w = w_
w.append(w_)
v.append(v_)
# N <= 30
def solve1():
global n, W, items
# 半分全列挙
a = n // 2
b = n - a
items1 = []
items2 = []
for i in range(2 ** a):
w_ = 0
v_ = 0
for j in range(a):
if i & 2**j > 0:
w_ += w[j]
v_ += v[j]
items1.append([w_, v_])
items1 = sorted(items1, key=lambda x: (x[0], -x[1]))
for i in range(2 ** b):
w_ = 0
v_ = 0
for j in range(b):
if i & 2**j > 0:
w_ += w[a+j]
v_ += v[a+j]
items2.append([w_, v_])
items2 = sorted(items2, key=lambda x: (x[0], -x[1]))
a_items = []
pre_v = 0
for i in range(len(items1)):
if items1[i][0] > W:
break
if items1[i][1] > pre_v:
a_items.append(items1[i])
pre_v = items1[i][1]
a_items.insert(0, [0, 0])
b_items = []
pre_v = 0
for i in range(len(items2)):
if items2[i][0] > W:
break
if items2[i][1] > pre_v:
b_items.append(items2[i])
pre_v = items2[i][1]
b_items.insert(0, [0, 0])
b_items.append([10**20, 0])
b_w = [x[0] for x in b_items]
ans = 0
for i in range(len(a_items)):
w_ = W - a_items[i][0]
idx = bisect.bisect_left(b_w, w_) - 1
if a_items[i][0] + b_items[idx][0] <= W:
ans = max(ans, a_items[i][1] + b_items[idx][1])
idx = bisect.bisect_left(b_w, w_)
if a_items[i][0] + b_items[idx][0] <= W:
ans = max(ans, a_items[i][1] + b_items[idx][1])
print(ans)
# max_w <= 1000
def solve2():
global n, W, items
# wのdp
dp = [[0 for _ in range(W+1)]for _ in range(n+1)]
for i in range(n):
for j in range(w[i], W+1):
dp[i+1][j] = max(dp[i][j], dp[i+1][j-1], dp[i][j - w[i]] + v[i])
ans = 0
for i in range(W+1):
ans = max(ans, dp[-1][i])
# max_v <= 1000
def solve3():
global n, W, items
# vのdp
sum_v = 0
for i in range(n):
sum_v += v[i]
dp = [[INF for _ in range(sum_v+1)]for _ in range(n+1)]
for i in range(n):
dp[i][0] = 0
for j in range(v[i], sum_v+1):
dp[i+1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i])
ans = 0
for i in range(len(dp[-1])):
if W >= dp[-1][i]:
ans = i
print(ans)
if n <= 30:
solve1()
elif max_w <= 1000:
solve2()
else:
solve3()