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 <iostream>
#include <climits>
#include <set>
#include <string>
#include <algorithm>
#include <vector>
#define MAX 1000000001

using namespace std;
#define ll long long
#define dbg if(0)

ll val[40],wei[40],W;

void build(ll bg,ll en,vector< pair<ll,ll> > &t){
    ll m=en-bg;
    for(int i=0; i< (1 << m);i++){
        ll vt=0,wt=0;
        for(int j=0;j<m;j++){
            if( (i>>j) & 1){
                vt+=val[bg+j];
                wt+=wei[bg+j];
            }
        }
        if (wt>W)continue;
        t.push_back( pair<ll,ll>(wt,vt) );
    }
    sort(t.begin(),t.end());
    //無駄な組み合わせを上書きする
    ll vmax=0;
    for(int i=0;i < t.size();i++){
        vmax = max(vmax,t[i].second);
        t[i].second = vmax;
    }
}



int main(){
    ll n;
    cin >> n>> W ;
    vector< pair<ll,ll> > s1,s2;
    for(int i=0;i<n;i++){
        cin >>val[i]>>wei[i];
    }
    dbg cout<<"ghhh"<<endl;
    build(0,n/2,s1);
    dbg cout<<"ghhh"<<endl;
    build(n/2,n,s2);
    dbg cout <<s1.size()<<endl;
    ll ans=0;
    for(auto p1:s1){
        ll w1=p1.first , v1=p1.second , v2;
        v2=(lower_bound(s2.begin(),s2.end(),pair<ll,ll>(W-w1,LLONG_MAX))-1)->second;
        ans=max(ans,v1+v2);
    }

    cout <<ans<<endl;
    return 0;
}
