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
/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H&lang=jp
*/

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;


int main(){
    int n;
    ll W;
    cin >> n >> W;
    int n1,n2;
    n1 = n/2;
    n2 = n-n1;
    vector<ll> val(n);
    vector<ll> wei(n);
    rep(i,n){
        ll v,w;
        cin >> v >> w;
        val[i]=v;
        wei[i]=w;
    }

    /*
    cout << "value" << endl;
    for(auto v:val) cout << v << " ";
    cout << endl;
    */

    /*
    cout << "weight" << endl;
    for(auto w:wei) cout << w << " ";
    cout << endl;
    */

    //vector<P> sec;
    vector<P> fir(1<<n1);
    //first:weight  second:value

    rep(i,1<<n1){
        ll v=0,w=0;
        for(int j = 0;j<n1;++j){
            if(i>>j & 1){
                w += wei[j];
                v += val[j];
            }
        }
        fir[i].first = w;
        fir[i].second = v;
    }

    sort(fir.begin(),fir.end());

    /*
    cout << "sorted" << endl;
    rep(i,1<<n1){
        cout << "w: " << fir[i].first << "v: " << fir[i].second << endl;
    }
    */

    vector<ll> fir_defined_w;
    vector<ll> fir_defined_v;
    int m = 0;
    fir_defined_v.push_back(fir[0].second);
    fir_defined_w.push_back(fir[0].first);
    for(int i=1;i< 1<<n1; ++i){
        if(fir[m].second < fir[i].second) {
            m=i;
            //fir_defined.push_back(fir[i]);
            fir_defined_v.push_back(fir[i].second);
            fir_defined_w.push_back(fir[i].first);
        }
    }

    /*
    cout << "eliminate" << endl;
    rep(i,fir_defined_w.size()){
        cout << "w: " << fir_defined_w[i]<< "v: " << fir_defined_v[i] << endl;
    }
    */



    //cout << "second" << endl;
    ll res=0;
    rep(i,1<<n2){
        ll v=0,w=0;
        for(int j = 0; j<n2;++j){
            if(i>>j & 1){
                w+=wei[j+n1];
                v+=val[j+n1];
            }
        }

        //cout << "w: " << w << "v: " << v << "res"<< res<< endl;


        
        if(w<=W){
            decltype(fir_defined_w)::iterator temp = lower_bound(fir_defined_w.begin(),fir_defined_w.end(),W-w+1);
            int idx;
            idx = distance(fir_defined_w.begin(),temp);
            if(idx==0) idx++; 
            res = max(res,v+  fir_defined_v[idx-1]);
            //cout << "sec" << fir_defined_v[idx-1] << endl;
            //cout << "temp:idx " <<idx<<" " << res << endl;
        }
        
    }

    cout << res << endl;
}
