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<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> P;
typedef long long int ll;
typedef pair<ll,ll> LLP;

ll INF = LLONG_MAX;

#define ARRAY_MAX 15

void build(ll first,ll last,vector<ll>& value,vector<ll>& weight,vector<LLP> &arr,ll weight_maxi){

    ll times = last - first;
    for(int i = 0;i < (1<<times);i++){

        ll va = 0,we = 0;
        for(int j = 0;j < times;j++){
            
            if((i>>j)&1){
                //選ぶ
                va += value[first + j];
                we += weight[first + j];
            }
        }
        if(we > weight_maxi){
            continue;
        }
        arr.push_back({we,va});
    }
    VSORT(arr);

    ll v_max = 0;
    REP(i,arr.size()){
        v_max = max(v_max,arr[i].second);
        arr[i].second = v_max;
    }
}




int main(){

    ll n,weight_maxi;
    cin >> n >> weight_maxi;
    vector<ll> value(n),weight(n);
    REP(i,n){
        cin >> value[i] >> weight[i];
    }

    vector<LLP> s1,s2;

    build(0,n/2,value,weight,s1,weight_maxi);//前半部分
    build(n/2,n,value,weight,s2,weight_maxi);//後半部分
    ll ans = -1;

    REP(i,s1.size()){
        ll w1 = s1[i].first,v1 = s1[i].second,v2;
        v2 = (lower_bound(s2.begin(),s2.end(),LLP(weight_maxi-w1,INF))-1)->second;
        ans = max(ans,v1+v2);
    }
    cout << ans << endl;



    return 0;
}
