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;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX_N = 40;
int N;
ll W, w[MAX_N], v[MAX_N];
pll ps[1 << (MAX_N/2)];

int main() {
    cin >> N >> W;
    rep(i, N) cin >> v[i] >> w[i];

    int n2 = N / 2;
    for (int i = 0; i < 1<<n2; i++) {
        ll sw = 0, sv = 0;
        for (int j = 0; j < n2; j++) {
            if (i >> j & 1) {
                sw += w[j];
                sv += v[j];
            }
        }
        ps[i] = make_pair(sw, sv);
    }

    sort(ps, ps+(1<<n2));
    int m = 1;
    for (int i = 1; i < (1<<n2); i++) {
        if (ps[m-1].second < ps[i].second) {
            ps[m++] = ps[i];
        }
    }

    ll res = 0;
    for (int i = 0; i < 1 << (N - n2); i++) {
        ll sw = 0, sv = 0;
        for (int j = 0; j < N - n2; j++) {
            if (i >> j & 1) {
                sw += w[n2+j];
                sv += v[n2+j];
            }
        }
        if (sw <= W) {
            ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, LLINF))-1)->second;
            res = max(res, sv + tv);
        }
    }
    cout << res << endl;
}

