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;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()


ll n, W, v[45], w[45];
 
void build(int bg, int en, vector<P> &t){
    int _n = en - bg;
    for(int i = 0; i<(1<<_n); ++i){
        ll vt = 0, wt = 0;
        for(int j = 0; j<_n; ++j){
            if((i>>j)&1){
                vt += v[bg+j];
                wt += w[bg+j];
            }
        }
        if(wt>W)continue;
        t.push_back({wt,vt});
    }
    SORT(t);
    ll vmax = 0;
    for(int i=0;i<t.size();++i){
        if(t[i].second < vmax)t[i].second = vmax;
        vmax = max(vmax, t[i].second);
    }
}
 

int main() {
    cin >> n >> W;
    REP(i,n){
        cin >> v[i] >> w[i];
    }
    vector<P> t[2];
    build(0,n/2,t[0]);
    build(n/2,n,t[1]);
    ll ans = 0;
    for(auto p : t[0]){
        auto q = *--upper_bound(ALL(t[1]),P(W-p.first,LLINF));
        ans = max(ans, p.second + q.second);
    }
    cout << ans << endl;
    return 0;
}

