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>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef pair<long, long> P;

int main(){
    int n; long W; cin >> n >> W;
    long v[n], w[n]; rep(i, n) cin >> v[i] >> w[i];
    vector<P> s1((int)(pow(2, n/2))), s2((int)(pow(2, n-n/2)));
    rep(i, pow(2, n/2)){
        P t = P(0, 0);
        rep(j, n/2)if((i>>j)&1) t.first += w[j], t.second += v[j];
        s1[i] = t;
    }
    rep(i, pow(2, n-n/2)){
        P t = P(0, 0);
        rep(j, n-n/2)if((i>>j)&1) t.first += w[n/2+j], t.second += v[n/2+j];
        s2[i] = t;
    }
    sort(s1.begin(), s1.end(), [](const P &a, const P &b){ if(a.first==b.first){return a.second > b.second;} else return a.first < b.first;});
    long cur1 = s1[0].first; long cur2 = s1[0].second;
    cur1 = cur2 = 0;
    rep(i, pow(2, n/2)){
        if(cur1<=s1[i].first && cur2>=s1[i].second) s1[i].first = cur1, s1[i].second = cur2; 
        cur1 = s1[i].first; cur2 = s1[i].second;
    }
    s1.push_back(P(-(1e17), 0)); s1.push_back(P(W+1, 0));
    sort(s1.begin(), s1.end(), [](const P &a, const P &b){ if(a.first==b.first){return a.second > b.second;} else return a.first < b.first;});
    long ans = 0;
    rep(i, pow(2, n-n/2)){
        int ok = 0; int ng = (int)(pow(2, n/2)) + 1;
        while(ng - ok > 1){
            int mid = (ok + ng) / 2;
            if(s1[mid].first+s2[i].first <= W) ok = mid;
            else ng = mid;
        }
        if(ok != 0) ans = max(ans, s1[ok].second + s2[i].second);
    }
    cout << ans << endl;
}
