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
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  ll n,W; cin >> n >> W;
  vector<ll> v(n);
  vector<ll> w(n);
  vector<pll> a(0);
  vector<pll> b(0);
  rep(i,n){
    cin >> v[i] >> w[i];
  }
  rep(i,1<<(n/2)){
    ll va=0,wa=0;
    rep(j,n/2){
      if((i>>j)&1){
        va+=v[j];
        wa+=w[j];
      }
    }
    a.push_back(pll(wa,va));
  }
  rep(i,1<<(n-n/2)){
    ll vb=0,wb=0;
    rep(j,n-n/2){
      if((i>>j)&1){
        vb+=v[j+n/2];
        wb+=w[j+n/2];
      }
    }
    b.push_back(pll(wb,vb));
  }
  sort(all(a));
  sort(all(b));
  rep(i,b.size()-1){
    chmax(b[i+1].second,b[i].second);
  }
  ll ans=0;
  for(int i=0,j=b.size()-1;i<a.size();i++){
    while(a[i].first+b[j].first>W){
      j--;
      if(j<0) goto OUT;
    }
    chmax(ans,a[i].second+b[j].second);
  }
OUT:
  cout << ans << endl;
}
