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
// Knapsack, Huge
// AOJ DPL 1H
#include    <bits/stdc++.h>
using   namespace   std;
typedef long long ll;

#define INF (1<<30)

#define Rep0(i, n)  for (int i=0; i<n; i++)
#define Rep1(i, n)  for (int i=1; i<=n; i++)

struct  Item {
    ll  v=0;
    ll  w=0;
};

void    Fun(int l, int r, vector<Item> &I, vector<vector<ll>> &V) {
    ll N=(1<<(r-l));
    for (ll i=0; i<N; i++) {
        ll v=0;
        ll w=0;
        ll II=i;
        for (int j=l; j<r; j++) {
            if (1==II%2) {
                v +=I.at(j).v;
                w +=I.at(j).w;
            }
            II/=2;
        }
        V.push_back({w, v});
    }
    return;
}

int main() {
    int N;
    ll W;
    cin >>N >>W;
    vector<Item> I(N);
    Rep0(i, N)
        cin >>I.at(i).v >>I.at(i).w;
    vector<vector<ll>> F;
    vector<vector<ll>> B;
    Fun(0, N/2, I, F);
    Fun(N/2, N, I, B);
    sort(F.begin(), F.end());
    sort(B.begin(), B.end());
    for (ll i=1; i<F.size(); i++)
        F.at(i).at(1)=max(F.at(i).at(1), F.at(i-1).at(1));
    for (ll i=1; i<B.size(); i++)
        B.at(i).at(1)=max(B.at(i).at(1), B.at(i-1).at(1));
    ll S=0;
    ll ixf=F.size()-1;
    ll ixb=0;
    for(;;) {
        if (W>=F.at(ixf).at(0)+B.at(ixb).at(0)) {
            S=max(S, F.at(ixf).at(1)+B.at(ixb).at(1));
            ixb++;
        } else
            ixf--;
        if (0>ixf)
            break;
        if (B.size()==ixb)
            break;
    }
    cout <<S <<endl;
    return 0;
}

