You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 40
* 1 ≤ vi ≤ 1015
* 1 ≤ wi ≤ 1015
* 1 ≤ W ≤ 1015

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9
n, W = map(int, input().split())
value = []
weight = []

n1 = n // 2
n2 = n - n1

vw1 = [[0, 0]]
vw2 = [[0, 0]]

for _ in range(n1):
  v, w = map(int, input().split())
  sz = len(vw1)
  for i in range(sz):
    p = vw1[i][:]
    p[0] += w
    p[1] += v
    vw1.append(p)

for _ in range(n2):
  v, w = map(int, input().split())
  sz = len(vw2)
  for i in range(sz):
    p = vw2[i][:]
    p[0] += w
    p[1] += v
    vw2.append(p)

vw1.sort()
vw2.sort()

maxv = 0
for i in range(2 ** (n - n // 2)):
  w, v = vw2[i]
  if maxv < v:
    maxv = v
  else:
    vw2[i][1] = maxv


ind1 = 0
ind2 = 2 ** (n - n // 2) - 1
ans = 0
while ind1 < 2 ** (n // 2) and ind2 >= 0:
  w1, v1 = vw1[ind1]
  w2, v2 = vw2[ind2]
  while ind2 > 0 and w1 + w2 > W:
    ind2 -= 1
    w2, v2 = vw2[ind2]
  if w1 + w2 <= W:
    ans = max(ans, v1 + v2)
  ind1 += 1

print(ans)
