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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (in i = 0; i < (in)(n); i++)
#define REP(i,a,b) for(in i=(in)(a);i<(in)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const in inf=1e9+7;
using P=pair<in,in>;
vector<in> dx={0,1,-1,0};
vector<in> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    in n,m;
    cin>>n>>m;
    vector<P> a(n);
    rep(i,n) cin>>a[i].first>>a[i].second;
    vector<P> wv1(0),wv2(0);
    for(in tmp = 0;tmp< (1<<(n/2)); tmp++){
        bitset<20> s(tmp);
        in w=0,v=0;
        rep(i,n/2){
            if(!s.test(i)) continue;
            v +=a[i].first;
            w +=a[i].second;
        }
        if(w>m) continue;
        wv1.emplace_back(w,v);
    }
    for(in tmp = 0;tmp< (1<<(n-n/2)); tmp++){
        bitset<20> s(tmp);
        in w=0,v=0;
        rep(i,n-n/2){
            if(!s.test(i)) continue;
            v +=a[n/2+i].first;
            w +=a[n/2+i].second;
        }
        if(w>m) continue;
        wv2.emplace_back(w,v);
    }
    sort(all(wv1));
    sort(all(wv2));
    vector<P> w1(0),w2(0);
    in w=-1,v=-1;
    rep(i,wv1.size()){
        if(i<wv1.size()-1 && wv1[i].first==wv1[i+1].first) continue;
        in ww,vv;
        tie(ww,vv)=wv1[i];
        if(vv>v){
            v=vv;
            w1.emplace_back(ww,vv);
        }
    }
    v=-1;
    rep(i,wv2.size()){
        if(i<wv2.size()-1 && wv2[i].first==wv2[i+1].first) continue;
        in ww,vv;
        tie(ww,vv)=wv2[i];
        if(vv>v){
            v=vv;
            w2.emplace_back(ww,vv);
        }
    }
    in ans=0;
    rep(i,w1.size()){
        in x,y;//weight,value
        tie(x,y)=w1[i];
        y += (*(lower_bound(all(w2),P(m-x+1,0))-1)).second;
        ans =max(ans,y);
    }
    cout<<ans<<endl;
}/*
./problem.exe
*/
