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 d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const double EPS = 1e-10;

int main() {
    lint N, W;
    cin >> N >> W;

    vector<lint> wa, va;
    vector<lint> wb, vb;

    rep(i, N) {
        lint tmp_w, tmp_v;
        cin >> tmp_v >> tmp_w;
        if (i < N / 2) {
            wa.push_back(tmp_w), va.push_back(tmp_v);
        } else {
            wb.push_back(tmp_w), vb.push_back(tmp_v);
        }
    }

    // for (int i = 0; i < wa.size(); i++) {
    //     cout << wa[i] << ' ' << va[i] << endl;
    // }
    // for (int i = 0; i < wb.size(); i++) {
    //     cout << wb[i] << ' ' << vb[i] << endl;
    // }

    vector<pair<lint, lint>> C;
    for (int bit = 0; bit < (1 << va.size()); bit++) {
        lint sum_w = 0, sum_v = 0;
        for (int i = 0; i < va.size(); i++) {
            if (bit & (1 << i)) {
                sum_v += va[i];
                sum_w += wa[i];
            }
        }
        C.push_back({sum_w, sum_v});
    }

    sort(all(C));

    vector<pair<lint, lint>> E;
    E.push_back(C[0]);
    for (int i = 1; i < C.size(); i++) {
        if (i == C.size() - 1) {
            if (C.back().second > C[i].second) {
                continue;
            } else {
                E.push_back(C[i]);
            }
            continue;
        } else if (C[i + 1].first == C[i].first) {
            continue;
        } else {
            // dd(C[i].first, C[i].second);
            if (E.back().second > C[i].second) {
                continue;
            } else {
                E.push_back(C[i]);
            }
        }
    }
    // for (auto p : C) {
    //     cout << p.first << '-' << p.second << endl;
    // }
    // for (auto p : E) {
    //     cout << p.first << ' ' << p.second << endl;
    // }

    lint ans = -1;
    for (int bit = 0; bit < (1 << wb.size()); bit++) {
        lint sum_w = 0, sum_v = 0;
        for (int i = 0; i < wb.size(); i++) {
            if (bit & (1 << i)) {
                sum_v += vb[i];
                sum_w += wb[i];
            }
        }
        auto idx = upper_bound(E.begin(), E.end(), make_pair(W - sum_w, LINF)) -
                   E.begin();

        if (idx == 0) continue;

        ans = max(ans, sum_v + E[idx - 1].second);

        // dd(sum_w, sum_v);
        // dd(idx, ans);
    }
    cout << ans << endl;

    return 0;
}
