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> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;} return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;} return false;
}

const int MAX_V=1e4+10;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; ll W; cin >> N >> W;
    vector<ll> v(N),w(N);
    rep(i,N) cin >> v[i] >> w[i];
    map<ll,ll> m1,m2;
    int n=N/2;
    rep(bit,1<<n){
        ll sumv=0,sumw=0;
        rep(i,n) if (bit&1<<i) sumv+=v[i],sumw+=w[i];
        if (sumw>W) continue;
        chmax(m1[sumw],sumv);
    }
    rep(bit,1<<(N-n)){
        ll sumv=0,sumw=0;
        rep(i,N-n) if (bit&1<<i) sumv+=v[i+n],sumw+=w[i+n];
        if (sumw>W) continue;
        chmax(m2[sumw],sumv);
    }
    ll M=0;
    set<ll> s;
    s.insert(0);
    for (auto x:m2) chmax(m2[x.first],M),chmax(M,x.second),s.insert(x.first);
    ll ans=0;
    for (auto x:m1){
        auto itr=s.upper_bound(W-x.first); --itr;
        chmax(ans,x.second+m2[*itr]);
    }
    cout << ans << endl;
}
