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;
using ll = long long;

template<class T>
vector<T> subvector(vector<T> a, int l, int num) {
   vector<T> ret;
   for(int i = l; i < l + num && i < (int)a.size(); i++)ret.emplace_back(a[i]);
   return ret;
}

vector<pair<ll,ll>> f(vector<pair<ll,ll>> a) {
    int n = a.size();
    vector<pair<ll,ll>> res;
    for(int i = 0; i < (1<<n); i++) {
        ll sumval = 0, sumcos = 0;
        for(int j = 0; j < n; j++) {
            if(i & (1 << j)) {
                sumval += a[j].first;
                sumcos += a[j].second;
            }
        }
        res.emplace_back(sumcos, sumval);
    }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n; ll w; cin >> n >> w;
    vector<pair<ll,ll>> a(n); // valuse, cost
    for(int i = 0; i < n; i++)cin >> a[i].first >> a[i].second; 
    int fn = n / 2, bn = n - n / 2;
    vector<pair<ll,ll>> fr, bc;
    fr = f(subvector(a,0, fn));
    bc = f(subvector(a,fn, bn));



    int m = bc.size();
    for(int i = 1; i < m; i++) {
        bc[i].second = max(bc[i].second, bc[i - 1].second);
    }


    ll ans = 0;
    for(auto i : fr) { //first : cost / second : value
        ll cur = w - i.first; //cur以下のものしか入らない
        auto itr = lower_bound(bc.begin(), bc.end(), pair<ll,ll>(cur+1, -1e18));
        if(itr == bc.begin())continue;
        itr--;
        ans = max(i.second + itr->second, ans);
    }
    cout << ans << endl;
}
