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>

using namespace std;

typedef long long ll;

struct Node {
    ll sumw, sumv;
    Node(ll sumw = 0, ll sumv = 0):sumw(sumw), sumv(sumv){
    }
};


void process(vector<ll>& w, vector<ll>& v,  int l, int r, vector<Node>& result) {
    int size = r - l + 1;
    int bound = (1 << size) - 1;
          
    for (int i = 0; i <= bound; i++) {
        ll sumw = 0;
        ll sumv = 0;
        for (int k = 0; k < size; k++) {
            if ((i & (1 << k)) > 0) {
                sumw += w[l + k];
                sumv += v[l + k];
            }
        }
        result.push_back(Node(sumw, sumv));
    }
}

bool cmp1(const Node& a, const Node &b) {
    return a.sumw < b.sumw || (a.sumw == b.sumw && a.sumv > b.sumv);
}

bool cmp2(const Node& a, const Node &b) {
    return a.sumw < b.sumw;
}

//sort vector w in increasing order and by v in decreasing order and.
//Create a new list where if w1 > w2 then v1 > v2.
void createMonoQueue(vector<Node>& a, vector<Node>& mono) {
    sort(a.begin(), a.end(), cmp1);
    ll curv = -1;
    for (Node& node : a) {
        if (node.sumv > curv) {
            mono.push_back(node);
            curv = node.sumv;
        }
    }
}

int main() {
    int n;
    ll c; 
    cin >> n >> c;
    
    vector<ll> v(n);
    vector<ll> w(n);
    
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i];
    }
    
    vector<Node> result1, result2;
    
    int m = (n - 1)/2;
    
    process(w, v, 0, m, result1);
    process(w, v, m + 1, n - 1, result2);
    
//    for (Node& node : result1) {
//        cout << node.sumw << " " << node.sumv << endl;
//    }
//    
//    cout << "second" << endl;
//    
//    for (Node& node : result2) {
//        cout << node.sumw << " " << node.sumv << endl;
//    }
    
    vector<Node> mono;
    
    createMonoQueue(result2, mono);
    
    ll ans = 0;
    for (Node& node : result1) {
        //cout << node.sumv << " " << node.sumw << endl;
        auto it = upper_bound(mono.begin(), mono.end(), c - node.sumw, cmp2);
        if (it != mono.begin()) {
            it--;
            ans = max(ans, node.sumv + it->sumv);
        }
    }
    
    cout << ans << endl;
    
    
    return 0;    
}