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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

map<ll,ll> make(ll *vl, ll *wl, int size, ll weight){
    map<ll,ll> mmap = {{0,0}};
    map<ll,ll> keep = {{0,0}};
    mmap.clear();
    mmap[0]=0;
    REP(i,size){
        keep = mmap;
        for(auto j : keep){
            if(j.first + wl[i] > weight)continue;
            else if(mmap.find(j.first + wl[i]) != mmap.end()){
                mmap[j.first + wl[i]] = max(mmap[j.first + wl[i]], j.second + vl[i]);
            }
            else{
                mmap[j.first + wl[i]] = j.second + vl[i];
            }
        }
        
    }
    ll maxv = 0;
    map<ll,ll> ansmap = {};
    for(auto i : mmap){
        maxv = max(maxv, i.second);
        ansmap[i.first] = maxv;
    }
    return ansmap;
}

int main(){
    ll n,weight;
    ll v[45]={};
    ll w[45]={};
    cin>>n>>weight;
    REP(i,n)cin>>v[i]>>w[i];
    ll anum = n/2;
    ll bnum = n-n/2;
    ll v1[25]={}; ll v2[25]={};
    ll w1[25]={}; ll w2[25]={};
    REP(i,anum){
        v1[i] = v[i];
        w1[i] = w[i];
    }
    for(int i=anum; i<n; i++){
        v2[i-anum] = v[i];
        w2[i-anum] = w[i];
    }
    map<ll,ll> map1 = make(v1, w1, anum, weight);
    map<ll,ll> map2 = make(v2, w2, bnum, weight);

    ll maxval = 0;
    auto iter2 = map2.rbegin();

    for(auto i=map1.begin(); i!=map1.end(); ++i){
        ll w11 = i->first;
        ll v11 = i->second;
        while(iter2->first + w11 > weight){
            iter2++;
        }
        ll sum = v11 + iter2->second;
        if(maxval < sum) maxval = sum;
    }
    cout<<maxval<<endl;
}
