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
import bisect
 
n,maxw = map(int , input().split())
data1 = [[0,0]] #data1enu[i]:iのbitが立ってる品物の価値、重さの総和
data2 = [[0,0]]
nn = n // 2

for i in range(nn):
    v,w = map(int , input().split())
    sz = len(data1)
    for j in range(sz):
        ppp = data1[j][:]
        ppp[0] += w
        ppp[1] += v
        data1.append(ppp)

for i in range(n-nn):
    v,w = map(int , input().split())
    sz = len(data2)
    for j in range(sz):
        ppp = data2[j][:]
        ppp[0] += w
        ppp[1] += v
        data2.append(ppp)

data2.sort()
maxx = 0
ss = len(data2)
for i in range(ss):
    maxx = max(maxx , data2[i][1])
    data2[i][1] = maxx
ans = 0
ss = len(data1)
for i in range(ss):
    ww , vv = data1[i]
    if (ww > maxw) : continue
    amari = maxw - ww
    ans = max (ans , vv + data2[bisect.bisect_right(data2, [amari , float('inf')])-1][1])

print(ans)

