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;
typedef pair<int,int> P;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

int main(){
    ll n,W;cin>>n>>W;
    vector<pair<ll,ll>> vw(n);
    rep(i,n)cin>>vw[i].second>>vw[i].first;
    vector<pair<ll,ll>> a,b;
    a.push_back(make_pair(0ll,0ll));
    b.push_back(make_pair(0ll,0ll));
    rep(i,n/2){
        ll asz=a.size();
        rep(j,asz){
            if(a[j].first+vw[i].first<=W){
                a.push_back(make_pair(a[j].first+vw[i].first,a[j].second+vw[i].second));
            }
        }
    }
    rep(i,n/2,n){
        ll bsz=b.size();
        rep(j,bsz){
            if(b[j].first+vw[i].first<=W){
                b.push_back(make_pair(b[j].first+vw[i].first,b[j].second+vw[i].second));
            }
        }
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    ll asz=a.size();
    ll bsz=b.size();
    ll curmax=0;
    rep(i,bsz){
        if(curmax>b[i].second)b[i].second=curmax;
        curmax=b[i].second;
    }
    ll ans=0;
    
    rep(i,asz){
        if(a[i].first>W)continue;
        auto it=lower_bound(b.begin(),b.end(),make_pair(W-a[i].first+1,-1ll));
        --it;
        chmax(ans,a[i].second+(it->second));
    }
    cout<<ans<<endl;
}

    
