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;
using ll = long long;
 
#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
 
#define MOD 1000000007
void init();
void solve();

signed main()
{
    init();
    solve();
}

int N;
ll W;
vector<pair<ll, ll> > vec, sor;
vector<ll> v, w;

void init()
{
    cin >> N >> W;
    v.RS(N);
    w.RS(N);
    rep(i, N) cin >> v[i] >> w[i];
    vector<pair<ll, ll> > tmp;
    int a = N / 2;
    rep(i, 1 << a) {
        ll vt = 0, wt = 0;
        int t = i;
        int pos = 0;
        while (t) {
            if (t & 1) {
                wt += w[pos];
                vt += v[pos];
            }
            pos++;
            t >>= 1;
        }
        tmp.PB(MP(wt, -vt));
    }
    sort(all(tmp));
    ll mav = -1;
    for (auto x : tmp) {
        ll vt = -x.second;
        if (vt > mav) {
           mav = vt;
           sor.PB(MP(W - x.first, -x.second));
       } 
    }
    reverse(all(sor));
    a = N - a;
    rep(i, 1 << a) {
        ll vt = 0, wt = 0;
        int t = i;
        int pos = N / 2;
        while (t) {
            if (t & 1) {
                wt += w[pos];
                vt += v[pos];
            }
            pos++;
            t >>= 1;
        }
        vec.PB(MP(wt, vt));
    }
}

void solve()
{
    ll res = -1;
    for (auto x : vec) {
        ll wt = x.first;
        ll vt = x.second;
        if (wt > W) continue;
        auto t = *lower_bound(all(sor), MP(wt, -1LL));
        res = max(res, t.second + vt);
    }
    cout << res << endl;
}


