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 _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int N,W;
    cin>>N>>W;
    vi v(N),w(N);
    rep(i,N)cin>>v[i]>>w[i];
    vp a,b;
    int n=N/2;
    rep(i,1<<n){
        int sw=0,sv=0;
        rep(j,n){
            if((i>>j)&1)sw+=w[j],sv+=v[j];
        }
        a.pb({sw,sv});
    }
    int m=N-n;
    rep(i,1<<m){
        int sw=0,sv=0;
        rep(j,m){
            if((i>>j)&1)sw+=w[n+j],sv+=v[n+j];
        }
        b.pb({sw,sv});
    }
    SORT(a);
    SORT(b);
    Rep(i,1,1<<n)a[i].se=max(a[i].se,a[i-1].se);
    Rep(i,1,1<<m)b[i].se=max(b[i].se,b[i-1].se);
    int ans=0;
    rep(i,1<<n){
        auto p=upper_bound(all(b),mp(W-a[i].fi,inf));
        if(p==b.begin())continue;
        p--;
        ans=max(ans,a[i].se+p->se);
    }
    cout<<ans<<endl;
}
