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;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  lint W; cin >> W;
  V<lint> v(n), w(n); for (int i = 0; i < n; ++i) cin >> v[i] >> w[i];
  int n0 = n >> 1, n1 = n - n0;
  struct S { lint v, w; };
  V<S> a0(1 << n0);
  for (int bit = 0; bit < 1 << n0; ++bit) for (int i = 0; i < n0; ++i) if (bit & 1 << i) a0[bit].v += v[i], a0[bit].w += w[i];
  V<S> a1(1 << n1);
  for (int bit = 0; bit < 1 << n1; ++bit) for (int i = 0; i < n1; ++i) if (bit & 1 << i) a1[bit].v += v[i + n0], a1[bit].w += w[i + n0];
  sort(begin(a1), end(a1), [](const S& lhs, const S& rhs) { return lhs.w < rhs.w; });
  V<lint> mx(1 << n1 | 1);
  for (int bit = 0; bit < 1 << n1; ++bit) mx[bit + 1] = max(mx[bit], a1[bit].v);
  lint res = 0;
  for (int bit = 0; bit < 1 << n0; ++bit) if (a0[bit].w <= W) res = max(res, a0[bit].v + mx[distance(begin(a1), lower_bound(begin(a1), end(a1), W - a0[bit].w + 1, [](const S& lhs, lint rhs) { return lhs.w < rhs; }))]);
  cout << res << '\n';
}
