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>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N, W;
  cin >> N >> W;
  vll v(N), w(N);
  for(int i = 0; i < N; i++){
    cin  >> v.at(i) >> w.at(i);
  }
  ll N1 = N/2;
  ll N2 = N - N1;
  vector<Pll> p1(0), p2(0);
  for(int bit = 0; bit < (1<<N1); bit++){
    ll vv = 0LL, ww = 0LL;
    for(int i = 0; i < N1; i++){
      if((bit>>i)&1){
        vv += v.at(i);
        ww += w.at(i);
      }
    }
    p1.push_back(Pll(ww, vv));
  }
  for(int bit = 0; bit < (1<<N2); bit++){
    ll vv = 0LL, ww = 0LL;
    for(int i = 0; i < N2; i++){
      if((bit>>i)&1){
        vv += v.at(N1+i);
        ww += w.at(N1+i);
      }
    }
    p2.push_back(Pll(ww, vv));
  }
  sort(ALL(p1)); sort(ALL(p2));
  ll tmp = p1.at(0).second;
  for(int i = 1; i < sz(p1); i++){
    if(p1.at(i).second > tmp) tmp = p1.at(i).second;
    else p1.at(i).second = tmp;
  }
  tmp = p2.at(0).second;
  for(int i = 1; i < sz(p2); i++){
    if(p2.at(i).second > tmp) tmp = p2.at(i).second;
    else p2.at(i).second = tmp;
  }
  ll ans = 0LL;
  for(int i = 0; i < sz(p1); i++){
    ll x = p1.at(i).second;
    ll maxi = W - p1.at(i).first;
    auto ite = lower_bound(ALL(p2), Pll(maxi+1, 0));
    if(ite == p2.begin()) continue;
    ite--;
    Pll y = *ite;
    chmax(ans, x + y.second);
  }
  cout << ans << endl;
}

