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;
#define ll long long
typedef pair<ll,ll> P;
ll dp[1<<22]={};
int main(){
  ll n,W,a,b;
  vector<ll> v[2],w[2];
  cin>>n>>W;
  for(ll i=0;i<n;i++){
    cin>>a>>b;
    v[i%2].push_back(a);
    w[i%2].push_back(b);
  }
  vector<P> an[2];
  for(ll cn=0;cn<2;cn++)
    for(ll i=0;i< (1<<v[cn].size());i++){
      ll suw=0,suv=0;
      for(ll j=0;j<v[cn].size();j++){
	if((1&(i>>j))==1){
	  suw+=w[cn][j];
	  suv+=v[cn][j];
	}
      }
      an[cn].push_back(P(suw,suv));
    }
  sort(an[0].begin(),an[0].end());
  ll ma=0;
  for(int i=0;i<an[0].size();i++){
    ma=max(ma,an[0][i].second);
    dp[i]=ma;
  }
  ll ans=0;
  for(int i=0;i<an[1].size();i++){
    ll vv=an[1][i].second;
    ll ww=an[1][i].first;
    ll lb=-1,ub=an[0].size(),mid;
    while(ub-lb>1){
      mid=(ub+lb)/2;
      if(an[0][mid].first+ww<=W)lb=mid;
      else ub=mid;
    }
    if(lb!=-1)ans=max(ans,vv+dp[lb]);
  }
  cout<<ans<<endl;
  return 0;
}

