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;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;
typedef pair<ll, ll> PL;
int main() {
  int n;
  ll W;
  cin >> n >> W;
  vector<ll> v(n), w(n);
  rep(i,n) cin >> v[i] >> w[i];
  int m = n - n / 2;
  n /= 2;

  vector<PL> p; 
  vector<ll> idx;
  
  for (int s = 0; s < (1 << n); s++) {
    ll sumv = 0, sumw = 0;
    for (int i = 0; i < n; i++) {
      if (s & (1 << i)) {
        sumv += v[i];
        sumw += w[i];
      }
    }
    idx.emplace_back(sumw);
    p.emplace_back(make_pair(sumw, sumv));
  }
  
  sort(idx.begin(), idx.end());
  idx.erase(unique(idx.begin(), idx.end()), idx.end());
  vector<ll> cum(idx.size() + 2, 0);
  
  for (int i = 0; i < p.size(); i++) {
    int j = lower_bound(idx.begin(), idx.end(), p[i].first) - idx.begin();
    cum[j + 1] = max(cum[j], p[i].second);
  }
  for (int i = 0; i < idx.size(); i++) {
    cum[i + 1] = max(cum[i], cum[i + 1]);
  }

  ll res = 0;
  
  for (int s = 0; s < (1 << m); s++) {
    ll sumw = 0, sumv = 0;
    for (int i = 0; i < m; i++) {
      int j = i + n;
      if (s & (1 << i)) {
        sumw += w[j];
        sumv += v[j];
      }
    }
    ll x = W - sumw;
    if (x < 0) continue;
    int r = upper_bound(idx.begin(), idx.end(), x) - idx.begin();
    res = max(res, sumv + cum[r]);
  }
  
  cout << res << endl;
  return 0;
} 
