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<ll, ll> P;

ll bit[20];
void make_bit(ll n){
    for(int i=0; i<20; i++){
        bit[i]=n%2;
        n /=2;
    }
}

bool comp(P &a, P &b){
    if(a.first !=b.first) return a.first < b.first;
    return a.second > b.second;
}
vector<P> Fir,Sec;

int main(){
    ll N; ll W;
    cin >> N >> W;
    ll v[40], w[40];
    for(ll i=0; i<N; i++){
        cin >> v[i] >> w[i];
    }
    for(ll i=0; i< pow(2,N/2); i++){
        make_bit(i);
        ll sum_v=0, sum_w=0;
        for(int j=0; j<20; j++){
            sum_v +=bit[j]*v[j];
            sum_w +=bit[j]*w[j];
        }
        Fir.push_back(P(sum_w, sum_v));
    }
    for(ll i=0; i< pow(2,(N+1)/2); i++){
        make_bit(i);
        ll sum_v=0, sum_w=0;
        for(int j=0; j<20; j++){
            sum_v +=bit[j]*v[j+N/2];
            sum_w +=bit[j]*w[j+N/2];
        }
        Sec.push_back(P(sum_w, sum_v));
    }
    
    sort(Sec.begin(),Sec.end()); //重み,価値の順
/*
    for(auto a:Fir){
        cout << a.first << " " << a.second << endl;
    }
    cout << 'a' << endl;

    for(auto a:Sec){
        cout << a.first << " " << a.second << endl;
    }
*/

    ll Max=0;
    for(P &a : Sec){
        Max=max(Max,a.second);
        a.second = Max;
    }
    reverse(Sec.begin(),Sec.end());
    sort(Fir.begin(),Fir.end()); //大きい順のFir



    ll Max_v=0;

    ll t=0;
    for(P b :Fir){
        ll v=b.second;
        ll w=b.first;
        while(t<Sec.size() && Sec.at(t).first + w > W) t++;
        if(t>=Sec.size()) break;
        Max_v = max(Max_v, Sec.at(t).second+v);
    }
/*    for(P b :Fir){
        auto itr = upper_bound(Sec.begin(), Sec.end(), W-b.first);
        ll c =(itr-1).second + b.second;
        Max_v = max(Max_v , c);
    }
*/
    cout << Max_v << endl;
}
