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>
#include <climits>

using namespace std;
typedef unsigned long long ull;

struct sort_cand
{
  bool operator()(const pair<ull,ull> &lhs, const pair<ull,ull> &rhs) {
    if (lhs.first == rhs.first) {
      return lhs.second > rhs.second;
    }
    else {
      return lhs.first < rhs.first;
    }
  }
};

void create_candidates(vector<ull>& v, vector<ull>& w, int lb, int ub, vector< pair<ull, ull> >& cand_vec) {
  if (lb > ub) {
    cand_vec.push_back(make_pair(0, 0));
    return;
  }

  int bits = ub - lb + 1;
  vector< pair<ull, ull> > tmp_cand;
  for (int i = 0; i < (1<<bits); ++i) {
    ull sv=0, sw=0;
    for (int j = 0; j < bits; ++j) {
      if (i & (1<<j)) {
        sv += v[lb+j];
        sw += w[lb+j];
      }
    }
    tmp_cand.push_back(make_pair(sw, sv));
  }

  sort(tmp_cand.begin(), tmp_cand.end(), sort_cand());

  int cand_idx = 0;
  cand_vec.push_back(tmp_cand[0]);
  for (int i = 1; i < (1<<bits); ++i) {
    if (cand_vec[cand_idx].second < tmp_cand[i].second) {
      cand_vec.push_back(tmp_cand[i]);
      cand_idx++;
    }
  }
}

int main() {
  ull N,W;
  vector<ull> v, w;
  cin>>N>>W;
  for (int i = 0; i < N; ++i) {
    ull vv, ww;
    cin>>vv>>ww;
    v.push_back(vv);
    w.push_back(ww);
  }

  int splt = N/2;
  vector< pair<ull, ull> > form_cand;
  create_candidates(v, w, 0, splt, form_cand);

  vector< pair<ull, ull> > latt_cand;
  create_candidates(v, w, splt+1, N-1, latt_cand);

  ull ans = 0;
  ull INF = ULLONG_MAX;
  for (int i = 0; i<form_cand.size(); ++i) {
    ull tmp_w = form_cand[i].first;
    ull tmp_v = form_cand[i].second;
    if (tmp_w <= W) {
      ull opt_latt = (lower_bound(latt_cand.begin(), latt_cand.end(), make_pair(W-tmp_w, INF))-1)->second;
      ans = max(ans, tmp_v+opt_latt);
    }
  }
  cout<<ans<<endl;

  return 0;
}
