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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define int long long
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
constexpr int INF = 1000000000000000000LL;
template<typename A, typename B> bool cmin(A &a, const B &b) { return b < a ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }

signed main() {
  int N, W;
  cin >> N >> W;
  vector<int> v(N), w(N);
  rep(i, N) cin >> v[i] >> w[i];
  int mid = N / 2;
  vector<pair<int, int>> left;
  rep(i, 1 << mid) {
    int sv = 0, sw = 0;
    rep(j, mid) if (i >> j & 1) sv += v[j], sw += w[j];
    left.emplace_back(sw, -sv);
  }
  sort(all(left));
  loop(i, 1, left.size()) cmin(left[i].second, left[i - 1].second);
  int maxi = 0;
  rep(i, 1 << (N - mid)) {
    int sv = 0, sw = 0;
    rep(j, N - mid) if (i >> j & 1) sv += v[j + mid], sw += w[j + mid];
    if (sw > W) continue;
    auto p = lower_bound(all(left), make_pair(W - sw, -INF));
    if (p == left.end()) --p;
    if (p->first + sw > W) --p;
    cmax(maxi, -p->second + sv);
  }
  cout << maxi << endl;
}

