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>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

static const ll INF = 1e15;

const ll mod = 1000000007;

map<ll, ll> knapsack_combination(const vector<ll> & w, const vector<ll> & v) {
	const int inv = -1;
	const int n = w.size();
	const ll shift = 1LL << w.size();
	vector<pair<ll, ll>> dp;
	for (ll i = 0; i < shift; i++) {
		ll wSum = 0;
		ll vSum = 0;
		for (ll j = 0; j < n; j++) {
			if (i & (1LL << j)) {
				wSum += w[j];
				vSum += v[j];
			}
		}
		dp.emplace_back(wSum, vSum);
	}
	sort(dp.begin(), dp.end());
	ll pv = -1;
    map<ll, ll> r;
	for (auto p : dp) {
		if (pv >= p.second) {
			continue;
		}
		r[p.first] = max(r[p.first], p.second);
		pv = r[p.first];
	}
	return r;
}


int main(void)
{
	ll N, W;
	cin >> N >> W;
	vector<ll> v1(N / 2), w1(N/2), v2(N - N / 2), w2(N - N / 2);
	for (int i = 0; i < N/2; i++) {
		cin >> v1[i] >> w1[i];
	}
	for (int i = 0; i < N - N / 2; i++) {
		cin >> v2[i] >> w2[i];
	}

	auto f = knapsack_combination(w1, v1);
	auto s = knapsack_combination(w2, v2);
	auto v = 0LL;
	for (auto p : f) {
		ll rest = W - p.first;
		auto l = s.upper_bound(rest);
		if (l != s.begin()) {
			std::advance(l, -1);
			v = max(v, p.second + l->second);
		}
	}
	cout << v << endl;
}

