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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;

bool comp(p left, p right){
  return left.first < right.first;
}

int main(){
  ll n,w;
  cin >> n >> w;
  p input[n];
  REP(i,n) cin >> input[i].second >> input[i].first;
  ll m = n/2;
  vector<p> first;
  vector<p> last;
  REP(i,1<<m){
    ll weight = 0, value = 0;
    REP(j,m){
      if(i>>j&1){
        weight += input[j].first;
        value += input[j].second;
      }
    }
    first.push_back(p(weight,value));
  }
  REP(i,1<<(n-m)){
    ll weight = 0, value = 0;
    REP(j,n-m){
      if(i>>j&1){
        weight += input[j+m].first;
        value += input[j+m].second;
      }
    }
    last.push_back(p(weight,value));
  }
  sort(first.begin(),first.end());
  sort(last.begin(),last.end());
  ll prev_v, prev_w;
  vector<p> first_cpy;
  REP(i,first.size()){
    if(i==first.size()-1||(i!=first.size()-1&&first[i].first<first[i+1].first)){
      if(i==0||first_cpy.back().second<first[i].second) first_cpy.push_back(p(first[i].first,first[i].second));
    }
    prev_w = first[i].first, prev_v = first[i].second;
  }
  vector<p> last_cpy;
  REP(i,last.size()){
    if(i==last.size()-1||(i!=last.size()-1&&last[i].first<last[i+1].first)){
      if(i==0||last_cpy.back().second<last[i].second) last_cpy.push_back(p(last[i].first,last[i].second));
    }
    prev_w = last[i].first, prev_v = last[i].second;
  }
  ll ans = 0;
  REP(i,first_cpy.size()){
    if(first_cpy[i].first>w) continue;
    ll itr = upper_bound(last_cpy.begin(),last_cpy.end(),p(w-first_cpy[i].first,0),comp)-last_cpy.begin();
    ans = max(ans, first_cpy[i].second+last_cpy[itr-1].second);
  }
  cout << ans << endl;
  return 0;
}

