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;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;ll W;cin>>n>>W;
    vll v(n),w(n);rep(i,n)cin>>v[i]>>w[i];
    if(n==1){
        if(w[0]<=W)cout<<v[0]<<endl;
        else cout<<0<<endl;
        return 0;
    }
    int k=n/2;
    vector<pair<ll,ll>> a,b,c;
    ll sumw,sumv;
    rep(i,(1<<k)){
        bitset<25> tmp(i);
        sumw=(ll)0;sumv=(ll)0;
        rep(j,k){
            if(tmp[j]){
                sumw+=w[j];
                sumv+=v[j];
            }
        }
        a.push_back(mp(sumw,sumv));
    }
    rep(i,(1<<n-k)){
        bitset<25> tmp(i);
        sumw=(ll)0;sumv=(ll)0;
        rep2(j,k,n){
            if(tmp[j-k]){
                sumw+=w[j];
                sumv+=v[j];
            }
        }
        c.push_back(mp(sumw,sumv));
    }
    sort(all(a));sort(all(c));
    ll tmp=(ll)0;
    rep(i,c.size()){
        if(i<c.size()-1&&c[i].first==c[i+1].first)continue;
        else if(c[i].second>tmp){
            b.push_back(c[i]);
            tmp=c[i].second;
        }
    }
    int l,r,m;ll ans=0;
    rep(i,a.size()){
        l=-1;r=b.size();
        while(r-l>1){
            m=(l+r)/2;
            if(a[i].first+b[m].first>W)r=m;
            else l=m;
        }
        if(l==-1)break;
        ans=max(ans,a[i].second+b[l].second);
    }
    cout<<ans<<endl;
}
