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 <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr long long INF = 1LL << 62;
constexpr int MOD = 1e9 + 7;
constexpr double EPS = 1e-10;

ll v[44], w[44];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    ll N, W; cin >> N >> W;
    REP(i,N) cin >> v[i] >> w[i];

    int n1 = N/2;
    int n2 = N - n1;
    vector<pair<ll,ll> > group;
    for(int bit = 0; bit < (1<<n1); ++bit) {
        ll value = 0, weight = 0;
        for(int i=0;i < n1;++i) {
            if(bit & (1<<i)) {
                value += v[i];
                weight += w[i];
            }
        }
        if(W < weight) continue;
        group.emplace_back(weight, value);
    }
    sort(group.begin(),group.end());

    int t = 1;
    for(int i=1; i < (int)group.size(); ++i) {
        if(group[t-1].second < group[i].second) group[t++] = group[i];
    }
    group.resize(t);

    ll ans = 0;
    for(int bit = 0; bit < (1<<n2); ++bit) {
        ll value = 0, weight = 0;
        for(int i=0; i < n2; ++i) {
            if(bit & (1<<i)) {
                value += v[n1 + i];
                weight += w[n1 + i];
            }
        }
        if(W < weight) continue;
        ll val = (lower_bound(group.begin(), group.end(), make_pair(W-weight, INF)) - 1)->second;
        ans = max(ans, val + value);
    }

    cout << ans << '\n';
    return 0;
}
