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;
typedef long long ll;
typedef pair<ll, ll> P;

vector<ll> v;
vector<ll> w;

void dfs(int i, int end, ll vTemp, ll wTemp, vector<P> &x)
{
    if (i == end)
    {
        x.push_back(make_pair(wTemp, vTemp)); //wでソートしたい
        return;
    }
    dfs(i + 1, end, vTemp, wTemp, x);
    dfs(i + 1, end, vTemp + v[i], wTemp + w[i], x);
}

int main(void)
{
    int n;
    ll w_max;
    cin >> n >> w_max;

    v.resize(n);
    w.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i] >> w[i];
    }

    vector<P> a;
    vector<P> b;
    dfs(0, n / 2, 0, 0, a);
    dfs(n / 2, n, 0, 0, b);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    ll temp_v = -1;
    for (auto ib = b.begin(); ib < b.end(); ++ib)
    {
        if(ib->second <= temp_v){
            auto ib_erase = ib;
            ib->second = temp_v;
        }else{
            temp_v = ib->second;  
        }  
    }

     long long score = 0;
    for (auto ia = a.begin(); ia < a.end(); ++ia)
    {
        if(w_max < ia->first) break;
        auto ib = upper_bound(b.begin(), b.end(), P(w_max - ia->first, 0), [](const P l, const P r){return l.first < r.first;}) - 1;
        score = max(score, ia->second + ib->second);
    }

    cout << score << endl;
    return 0;
}

