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;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
ll v[2][30], w[2][30];

int main() {
    init();
    ll N, W;
    cin >> N >> W;

    ll n[2] = {N / 2, (N + 1) / 2};
    rep(i, 2) rep(j, n[i]) cin >> v[i][j] >> w[i][j];

    vvc<pair<ll, ll>> dp(2, vc<pair<ll,ll>>(1 << 20));
    vc<pair<ll, ll>> A(1 << 20);

    rep(ni,2){
        ll nn = n[ni];
        rep(i, nn){
            ll dj = 0, ai = 0, ww = w[ni][i], vv = v[ni][i];
            rep(j,1<<i){
                while(dj < 1<<i and dp[ni][dj].first + ww <= dp[ni][j].first){
                    A[ai] = {dp[ni][dj].first + ww, dp[ni][dj].second + vv};
                    dj++, ai++;
                }
                A[ai] = dp[ni][j];
                ai++;
            }
            while(dj < 1<<i){
                A[ai] = {dp[ni][dj].first + ww, dp[ni][dj].second + vv};
                dj++, ai++;
            }
            swap(dp[ni], A);
        }

        ll tv = 0;
        rep(i,1<<nn){
            if (!chmax(tv, dp[ni][i].second)) dp[ni][i].second = tv;
        }
        
    }

    ll ans = 0, i1 = (1 << n[1]) - 1;
    rep(i, 1<<n[0]){
        ll ww = dp[0][i].first, vv = dp[0][i].second;
        if (ww > W) break;

        while (ww + dp[1][i1].first > W) i1--;

        chmax(ans, vv + dp[1][i1].second);
    }

    cout << ans << endl;

}
