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"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	ll W=in<ll>();
	vector<pair<ll,ll>> P(N);
	REP(i,N){
		P[i].first=in<ll>();
		P[i].second=in<ll>();
	}

	ll H=N/2;
	ll PH=1LL<<H;
	vector<pair<ll,ll>> S(PH);
	REP(i,PH){
		ll v=i;
		ll val=0,weight=0,index=0;
		while(v){
			if(v&1){
				weight += P[index].second;
				val += P[index].first;
			}
			v>>=1LL;
			index++;
		}
		S[i]=make_pair(val,weight);
	}
	sort(ALL(S),[](pair<ll,ll>& l,pair<ll,ll>& r){return l.second==r.second?l.first<r.first:l.second<r.second;});
	vector<pair<ll,ll>> R;
	R.emplace_back(S[0]);
	ll current = R[0].first;
	for(int i=1;i<PH;i++){
		if(S[i].first>current){
			R.emplace_back(S[i]);
			current = S[i].first;
		}
	}

	ll ans=0;
	ll F=1LL<<(N-H);
	REP(i,F){
		ll v=i;
		ll val=0,weight=0,index=0;
		while(v){
			if(v&1){
				weight += P[H+index].second;
				val += P[H+index].first;
			}
			v>>=1LL;
			index++;
		}
		auto res = upper_bound(ALL(R),make_pair(0,W-weight),PAIRCOMP(second,<));
		if(res!=R.begin()){
			ans = max(ans,(res-1)->first+val);
		}
	}
	out(ans);
	return 0;
}
