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;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll W;
    cin>>W;
    vector<ll> v(n),w(n);
    rep(i,n) cin>>v[i]>>w[i];
    int m=n/2;
    vector<P> cnt;
    rep(i,1<<m){
      ll sw=0,sv=0;
      rep(j,m){
        if(i&(1<<j)) sw+=w[j],sv+=v[j];
      }
      cnt.push_back(P(sw,sv));
    }
    sort(begin(cnt),end(cnt));
    ll k=1;
    FOR(i,1,1<<m){
      if(cnt[k-1].second<cnt[i].second){
        cnt[k++]=cnt[i];
      }
    }
    ll inf=1e16;
    ll ans=0;
    rep(i,1<<(n-m)){
      ll sw=0,sv=0;
      rep(j,n-m){
        if(i&(1<<j)){
          sw+=w[m+j];
          sv+=v[m+j];
        }
      }
      if(sw<=W){
        ll tv=(lower_bound(begin(cnt),begin(cnt)+k,P(W-sw,inf))-1)->second;
        ans=max(ans,sv+tv);
      }
    }
    cout<<ans<<endl;
}
