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

typedef long long ll;
using namespace std;
const ll INF = LLONG_MAX/3;

int main(){
    int n;
    ll W;
    cin >> n >> W;
    ll value[n];
    ll weight[n];
    for (int i = 0; i<n;i++){
        cin >> value[i] >> weight[i] ;
    }

    int hn = n/2;
    vector<pair <ll, ll> > sumList;

    for (int i=0;i<(1<<hn);i++){
        ll v_sum = 0;
        ll w_sum = 0;
        for (int j=0;j<hn;j++){
            if((i>>j)&1){
                v_sum += value[j];
                w_sum += weight[j];
            }
        }
        sumList.push_back(make_pair(w_sum, v_sum));
    }

    sort(sumList.begin(), sumList.end());
    vector<pair <ll, ll> > sumListOmitted;
    sumListOmitted.push_back(sumList[0]);
    int j=0;
    for (int i=1;i<sumList.size();i++){
        if(sumListOmitted[j].second < sumList[i].second){
            sumListOmitted.push_back(sumList[i]);
            j++;
        }
    }

    ll result = 0;
    for (int i=0;i<(1<<(n-hn));i++){
        ll v_sum = 0;
        ll w_sum = 0;
        for (int j=0;j<n-hn;j++){
            if ((i>>j)&1){
                v_sum += value[hn+j];
                w_sum += weight[hn+j];
            }
        }
        if (w_sum <= W){
            result = max(result, v_sum + (lower_bound(sumListOmitted.begin(), sumListOmitted.end(), make_pair(W-w_sum,INF))-1)->second);
        }
    }

    cout << result << endl;
    return 0;
}