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;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main(){
	int N;
	ll W;
	cin>>N>>W;
	ll w[N],v[N];
	rep(i,N) cin>>v[i]>>w[i];
	vector<pair<ll,ll>> p;
	int N2=N/2;
	for(int i=0;i<1<<N2;i++){
		ll sw=0,sv=0;
		for(int j=0;j<N2;j++){
			if(i>>j & 1){
				sw+=w[j];
				sv+=v[j];
			}
		}
		p.push_back(make_pair(sw,sv));
	}
	sort(all(p));
	int m=1;
	for(int i=1;i<1<<N2;i++){
		if(p[m-1].second<p[i].second){
			p[m]=p[i];
			m++;
		}
	}
	ll res=0;
	for(int i=0;i<1<<(N-N2);i++){
		ll sw=0,sv=0;
		for(int j=0;j<N-N2;j++){
			if(i>>j & 1){
				sw+=w[N2+j];
				sv+=v[N2+j];
			}
		}
		if(sw<=W){
			pair<ll,ll> _p=make_pair(W-sw,INF);
			ll tv=(lower_bound(p.begin(),p.begin()+m,_p)-1)->second;
			res=max(res,sv+tv);
		}
	}
	cout<<res<<endl;
}
