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 UL = unsigned long;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        UL N; cin >> N;
        ULL W; cin >> W;
        vector<pair<ULL, ULL>> VW(40); rep(i, N) cin >> VW[i].first >> VW[i].second;
        vector<pair<ULL, ULL>> WVS(1 << 20);
        vector<pair<ULL, ULL>> WVT(1 << 20);
        rep(i, 20) {
            rep(j, 1 << i) {
                WVS[j + (1 << i)] = { WVS[j].first + VW[i].second, WVS[j].second + VW[i].first };
                WVT[j + (1 << i)] = { WVT[j].first + VW[i + 20].second, WVT[j].second + VW[i + 20].first };
            }
        }
        sort(WVT.begin(), WVT.end());
        rep(i, (1 << 20) - 1) {
            WVT[i + 1].second = max(WVT[i + 1].second, WVT[i].second);
        }
        ULL ans = 0;
        rep(i, 1 << 20) {
            if (WVS[i].first > W) continue;
            UL l = 0, r = 1 << 20;
            while (l + 1 < r) {
                UL m = (l + r) >> 1;
                if (WVS[i].first + WVT[m].first <= W) l = m;
                else r = m;
            }
            ans = max(ans, WVS[i].second + WVT[l].second);
        }
        cout << ans << endl;
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}

