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 REP(i,n) for (int i=0;i<(n);++i)

using namespace std;

using ull = unsigned long long;

using Item = pair<ull, ull>; // (weight, value)

std::vector<Item> enumerate_items(const std::vector<Item> &items, const ull capacity) {

    std::vector<Item> a0{Item(0, 0)};
    for (const Item &item: items) {

        ull weight, value;
        tie(weight, value) = item;

        size_t N0 = a0.size();
        std::vector<Item> a1;
        for (size_t i = 0; i < N0; ++i) {
            ull w = a0[i].first + weight;
            if (w > capacity) break;
            ull v = a0[i].second + value;
            a1.emplace_back(w, v);
        }
        size_t N1 = a1.size();

        std::vector<Item> b{Item(0, 0)};
        size_t i0 = 1;
        size_t i1 = 0;
        while (true) {
            if (i0 == N0) {
                while (i1 < N1) {
                    b.push_back(a1[i1++]);
                }
                break;
            } else if (i1 == N1) {
                while (i0 < N0) {
                    b.push_back(a0[i0++]);
                }
                break;
            } else {
                if (a0[i0].first < a1[i1].first) {
                    b.push_back(a0[i0++]);
                    while (i1 < N1 && (b.back().first >= a1[i1].first || b.back().second >= a1[i1].second)) {
                        ++i1;
                    }
                } else if (a0[i0].first > a1[i1].first) {
                    b.push_back(a1[i1++]);
                    while (i0 < N0 && (b.back().first >= a0[i0].first || b.back().second >= a0[i0].second)) {
                        ++i0;
                    }
                } else {
                    if (a0[i0].second >= a1[i1].second) {
                        b.push_back(a0[i0++]);
                        ++i1;
                        while (i1 < N1 && (b.back().first >= a1[i1].first || b.back().second >= a1[i1].second)) {
                            ++i1;
                        }
                    } else if (a0[i0].second < a1[i1].second) {
                        b.push_back(a1[i1++]);
                        ++i0;
                        while (i0 < N0 && (b.back().first >= a0[i0].first || b.back().second >= a0[i0].second)) {
                            ++i0;
                        }
                    }
                }
            }
        }
        a0 = b;
    }
    return a0;
}

ull knapsack_small_items(const std::vector<Item> &items, ull capacity) {

    size_t N = items.size();
    size_t N0 = N / 2;

    std::vector<Item> a0 = enumerate_items(std::vector<Item>(items.begin(), items.begin() + N0), capacity);
    std::vector<Item> a1 = enumerate_items(std::vector<Item>(items.begin() + N0, items.end()), capacity);

    ull result = 0;
    size_t j = a1.size() - 1;
    for (const Item &item0: a0) {
        ull w0, v0;
        tie(w0, v0) = item0;
        ull res = capacity - w0;
        while (a1[j].first > res) {
            if (j == 0) {
                goto out_of_loop;
            }
            --j;
        }
        result = max(result, v0 + a1[j].second);
    }
out_of_loop:
    return result;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    ull W;
    cin >> N >> W;
    vector<Item> items(N);
    REP(i, N) {
        ull v, w;
        cin >> v >> w;
        items[i] = Item(w, v);
    }

    cout << knapsack_small_items(items, W) << endl;

    return 0;
}

