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 <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using ll = long long;
template <typename T>
constexpr T INF() { return std::numeric_limits<T>::max() / 2; }
int main()
{
    int N;
    ll W;
    std::cin >> N >> W;
    std::vector<ll> v(N), w(N);
    for (int i = 0; i < N; i++) { std::cin >> v[i] >> w[i]; }
    const int F = N / 2, L = N - F;
    const int fmask = 1 << F, lmask = 1 << L;
    using P = std::pair<ll, ll>;
    std::vector<P> f(fmask, {0LL, 0LL}), l(lmask, {0LL, 0LL});
    for (int i = 0; i < fmask; i++) {
        for (int j = 0; j < F; j++) {
            if (i & (1 << j)) { f[i].first += w[j], f[i].second += v[j]; }
        }
    }
    for (int i = 0; i < lmask; i++) {
        for (int j = 0; j < L; j++) {
            if (i & (1 << j)) { l[i].first += w[j + F], l[i].second += v[j + F]; }
        }
    }
    std::sort(f.begin(), f.end()), std::sort(l.begin(), l.end());
    std::vector<ll> fw(fmask), fv(fmask), lw(lmask), lv(lmask);
    for (int i = 0; i < fmask; i++) { fw[i] = f[i].first, fv[i] = f[i].second; }
    for (int i = 0; i < lmask; i++) { lw[i] = l[i].first, lv[i] = l[i].second; }
    for (int i = 1; i < fmask; i++) { fv[i] = std::max(fv[i], fv[i - 1]); }
    for (int i = 1; i < lmask; i++) { lv[i] = std::max(lv[i], lv[i - 1]); }
    ll ans = 0;
    for (int i = 0; i < fmask; i++) {
        const ll WR = W - fw[i];
        const int ind = std::upper_bound(lw.begin(), lw.end(), WR) - lw.begin();
        if (ind <= 0) { break; }
        ans = std::max(ans, fv[i] + lv[ind - 1]);
    }
    std::cout << ans << std::endl;
    return 0;
}
