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 <vector>
#include <algorithm>

using namespace std;
using LL = long long;

const LL INF = 1L << 61;

int main() {
    LL N, W, v[40]{0}, w[40]{0};
    cin >> N >> W;

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

    LL n2 = N / 2;
    vector<pair<LL, LL>> P; //重さ, 価値

    for (int i = 0; i < 1 << n2; i++) {
        LL v1 = 0, w1 = 0;
        for (int j = 0; j < n2; j++) {
            if (i >> j & 1) {
                v1 += v[j];
                w1 += w[j];
            }
        }
        P.emplace_back(w1, v1);
    }

    sort(P.begin(), P.end());

    int k = 1;
    for (int i = 0; i < 1 << n2; i++) {
        if (P[k - 1].second < P[i].second) {
            P[k++] = P[i];
        }
    }

    LL ans = 0;

    for (int i = 0; i < 1 << (N - n2); i++) {
        LL v1 = 0, w1 = 0;
        for (int j = 0; j < N - n2; j++) {
            if (i >> j & 1) {
                v1 += v[n2 + j];
                w1 += w[n2 + j];
            }
        }
        if (w1 <= W) {
            LL v2 = (lower_bound(P.begin(), P.begin() + k, make_pair(W - w1, INF)) - 1)->second;
            ans = max(ans, v1 + v2);
        }
    }

    cout << ans << endl;
}
