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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll W;
ll v[40],w[40];
void calc(ll val,ll wei,ll loc,ll end, vector<P>& list){
  if(W<wei) return;
  list.push_back(make_pair(wei,val));
  if(loc==end)return;
  calc(val,wei,loc+1,end,list);
  calc(val+v[loc],wei+w[loc],loc+1,end,list);
}
void erase_v(vector<P>& list){
  P tmp;
  ll val,wei;
  val=list[0].second;
  wei=list[0].first;
  sort(list.begin(),list.end());
  vector<P> true_list;
  for(auto i=list.begin();i!=list.end();i++){
    tmp = *i;
    if(tmp.first!=wei){
      true_list.push_back(make_pair(wei,val));
      wei=tmp.first;
      val=tmp.second;
    }else{
      val=max(val,tmp.second);
    }
  }
  true_list.push_back(make_pair(wei,val));
  val=true_list[0].second;
  for(auto it=true_list.begin();it!=true_list.end();){
    if(val>it->second){
      true_list.erase(it);
    }else{
      val=it->second;
      it++;
    }
  }
  list=true_list;
}
int main(){
  vector<P> fi,se,th,fo;
  ll n;
  ll tmp,ma_v,cnt=0;
  cin >> n >> W;
  fill(v,v+40,0);
  fill(w,w+40,0);
  for(int i=0;i<n;i++){
    cin >> v[i] >> w[i];
  }
  calc(0,0,0,10,fi);
  calc(0,0,10,20,se);
  calc(0,0,20,30,th);
  calc(0,0,30,40,fo);
  erase_v(fi);
  erase_v(se);
  erase_v(th);
  erase_v(fo);
  ma_v=0;
  for(int i=0;i<fi.size();i++){
    for(int j=0;j<se.size();j++){
      if(fi[i].first+se[j].first>W) break;
      for(int k=0;k<th.size();k++){
        if(fi[i].first+se[j].first+th[k].first>W) break;
        for(int l=0;l<fo.size();l++){
          tmp=fi[i].first+se[j].first+th[k].first+fo[l].first;
          if(tmp<=W){
            cnt++;
            tmp=fi[i].second+se[j].second+th[k].second+fo[l].second;
            ma_v=max(ma_v,tmp);
          }else{
            break;
          }
        }
      }
    }
  }
  cout << ma_v<<endl;
}

