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;
typedef pair<ll,ll> P;
ll v[40];//ナップザックにおける価値（最大化対象）
ll w[40];//ナップザックにおける重量（制約）
//半分全列挙
//[l,r)についてsum(w)<=mwを満たすすべての組み合わせを返す(重さ, 価値)
vector<P> rekkyo(int l,int r,ll mw)
{
	vector<P> ret;
	int cnt=r-l;
	for(ll bit=0;bit<(1LL<<cnt);bit++)
	{
		auto ele=make_pair(0LL,0LL);
		for(int i=0;i<cnt;i++)
		{
			ll tmp=(bit&(1LL<<i));
			if(tmp>0)
			{
				ele.first+=w[l+i];
				ele.second+=v[l+i];
			}
		}
		if(ele.first<=mw)
			ret.push_back(ele);
	}
	return ret;
}


int main()
{
	int n;
	ll tar;
	ll ans=0;
	cin>>n>>tar;
	for(int i=0;i<n;i++)
		cin>>v[i]>>w[i];
	vector<P> left;//左側n/2
	vector<P> right;//右側n/2
	left=rekkyo(0,n/2,tar);
	right=rekkyo(n/2,n,tar);
	sort(right.begin(),right.end());
	ll nowv=right[0].second;
	for(int i=0;i<right.size();i++)
	{
		if(nowv<right[i].second)
			nowv=right[i].second;
		else
			right[i].second=nowv;
	}
	for(int i=0;i<left.size();i++)
	{
		P p=left[i];
		auto itr=upper_bound(right.begin(),right.end(),P(tar-p.first+1,0));
		if(itr==right.begin())
			continue;
		itr--;
		if((*itr).first+p.first<=tar)
			ans=max(ans,p.second+(*itr).second);
	}
	cout<<ans<<endl;
	return 0;
}
