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 P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
const ll INF=1e18+7;
const ll MOD=1e9+7;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll N1,N2,W;
	cin >> N1 >> W;
	N2 = N1/2;
	N1 -= N2;
	vector<ll> v1,v2,w1,w2;
	vector<P> ans1,ans2;

	FOR(i,0,N1){
		ll v,w;
		cin >> v >> w;
		v1.push_back(v);
		w1.push_back(w);
	}
	FOR(i,0,N2){
		ll v,w;
		cin >> v >> w;
		v2.push_back(v);
		w2.push_back(w);
	}

	ans1.push_back({0,0});
	FOR(i,0,N1){
		vector<P> anst;
		for(P x:ans1){
			anst.push_back(x);
			anst.push_back({x.first+w1[i],x.second+v1[i]});
		}
		ans1 = anst;
	}
	SORT(ans1);
	vector<P> anst;
	set<ll> s;
	FORR(i,0,ans1.size()){
		if(s.count(ans1[i].first)==0){
			s.insert(ans1[i].first);
			anst.push_back(ans1[i]);
		}
	}
	ans1 = anst;
	REV(ans1);
	anst.clear();
	ll mv=-1;
	FOR(i,0,ans1.size()){
		if(ans1[i].second>mv){
			mv = ans1[i].second;
			anst.push_back(ans1[i]);
		}
	}
	ans1 = anst;



	ans2.push_back({0,0});
	FOR(i,0,N2){
		anst.clear();
		for(P x:ans2){
			anst.push_back(x);
			anst.push_back({x.first+w2[i],x.second+v2[i]});
		}
		ans2 = anst;
	}
	SORT(ans2);
	anst.clear();
	s.clear();
	FORR(i,0,ans2.size()){
		if(s.count(ans2[i].first)==0){
			s.insert(ans2[i].first);
			anst.push_back(ans2[i]);
		}
	}
	ans2 = anst;
	REV(ans2);
	anst.clear();
	mv = -1;
	FOR(i,0,ans2.size()){
		if(ans2[i].second>mv){
			mv = ans2[i].second;
			anst.push_back(ans2[i]);
		}
	}
	ans2 = anst;


	ll ans = 0;
	FOR(i,0,ans1.size()){
		ll v1i = ans1[i].second;
		ll w1i = ans1[i].first;
		P x1i = ans1[i];
		if(w1i>W)continue;
		P search = {W-w1i+1,0};
		ll i2 = POSL(ans2,search);
		P zero={0,0};
		if(ans2[i2]==zero)i2++;
		ans = max(ans,v1i+ans2[i2-1].second);
	}
	cout << ans << endl;
}

