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
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-04-24 14:56:05
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int flag = 0;
  for (auto e : vec) os << (flag++ ? ", " : "{") << e;
  return os << '}';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int flag = 0;
  for (auto e : st) os << (flag++ ? ", " : "{") << e;
  return os << '}';
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int flag = 0;
  for (auto e : mp) os << (flag++ ? ", " : "{") << e;
  return os << '}';
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

using pll = pair<int64, int64>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N; int64 W; cin >> N >> W;

  vector<int64> v(N), w(N);
  for (int i = 0; i < N; ++i) cin >> v[i] >> w[i];
  
  vector<pll> fv, bv;
  
  for (int bit = 0; bit < (1 << (N / 2)); ++bit) {
    int64 tv = 0, tw = 0;
    for (int i = 0; i < N / 2; ++i) {
      if (bit & (1 << i)) {
        tv += v[i], tw += w[i];
      }
    }
    fv.emplace_back(tw, tv);
  }

  for (int bit = 0; bit < (1 << (N - N / 2)); ++bit) {
    int64 tv = 0, tw = 0;
    for (int i = 0; i < N - N / 2; ++i) {
      if (bit & (1 << i)) {
        tv += v[i + N / 2], tw += w[i + N / 2];
      }
    }
    bv.emplace_back(tw, tv);
  }
  // {weight, value}
  sort(all(fv));
  sort(all(bv));

  debug(fv, bv);

  int m = bv.size();
  vector<int64> mx(m, 0);

  mx[0] = bv[0].second;
  for (int i = 1; i < m; ++i) {
    mx[i] = max(mx[i - 1], bv[i].second);
  }

  const int64 inf = 1e18;

  int64 ans = 0;

  for (auto e : fv) {
    int pos = distance(bv.begin(), upper_bound(all(bv), (pll){W - e.first + 1, -inf}));
    --pos;
    if (pos < 0) continue;
    ans = max(ans, e.second + mx[pos]);
  }

  cout << ans << endl;

  return 0;
}

