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;

typedef long long ll;
const ll INF=2e18+10;

int main()
{
    ll n,m;

    while(cin>>n>>m)
    {
        vector<ll> v(n+1),w(n+1);
        for(int i=0;i<n;i++)
        {
            cin>>v[i]>>w[i];
        }
        vector<pair<ll,ll> > a;
        for(int i=0;i<(1<<(n/2));i++)
        {
            ll sv=0,sw=0;
            for(int j=0;j<n/2;j++)
            {
                if((i>>j)&1)
                {
                    sv+=v[j];
                    sw+=w[j];
                }
            }
            a.push_back(make_pair(sw,sv));
        }
        sort(a.begin(),a.end());
        ll Max=-INF;
        for(int i=0;i<a.size();i++)
        {
            a[i].second=max(a[i].second,Max);
            Max=a[i].second;
        }
        ll ans=0;
        for(int i=0;i<(1<<(n-n/2));i++)
        {
            ll sv=0,sw=0;
            for(int j=0;j<n-n/2;j++)
            {
                if((i>>j)&1)
                {
                    sv+=v[j+n/2];
                    sw+=w[j+n/2];
                }
            }
            if(sw<=m)
            {
                ll tv=(upper_bound(a.begin(),a.end(),make_pair(m-sw,INF))-1)->second;
                ans=max(ans,tv+sv);
            }

        }
        cout<<ans<<endl;
    }

    return 0;
}

