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
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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; }
ll n,W;
V<P>dat;
V<P> top,back;
void make_top(int now,ll wei,ll val){
    if(now==(n+1)/2){
        if(wei<=W)top.emplace_back(wei,val);
        return ;
    }
    make_top(now+1,wei+dat[now].fi,val+dat[now].se);
    make_top(now+1,wei,val);
}
void make_back(int now,ll wei,ll val){
    if(now==n){
        if(wei<=W)back.emplace_back(wei,val);
        return ;
    }
    make_back(now+1,wei+dat[now].fi,val+dat[now].se);
    make_back(now+1,wei,val);
}
int main(){
    cin>>n>>W;
    dat.resize(n);
    for(int i=0;i<n;i++)cin>>dat[i].se>>dat[i].fi;
    sort(all(dat));
    make_top(0,0,0);
    make_back((n+1)/2,0,0);
    sort(all(top));
    sort(all(back));
   V<ll> ma(back.size(),0);
   ma[0]=back[0].se;
   for(int i=1;i<back.size();i++){
       ma[i]=max(ma[i-1],back[i].se);
   }
   ll ans=0;
   for(int i=0;i<top.size();i++){
       int ind=upper_bound(all(back),P(W-top[i].fi,inf))-back.begin();
       ind--;
       chmax(ans,top[i].se+ma[ind]);
   }
   cout<<ans<<"\n";
}
