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 <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int N; ll W;
int main() {
	cin >> N >> W;
	vector<ll> v(N), w(N);
	for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
	int lc = N / 2, rc = N - lc;
	vector<pair<ll, ll> > p;
	for (int i = 0; i < 1 << lc; i++) {
		ll sv = 0, sw = 0;
		for (int j = 0; j < lc; j++) {
			if (i & (1 << j)) sv += v[j], sw += w[j];
		}
		if (sw <= W) p.push_back(make_pair(sw, sv));
	}
	sort(p.begin(), p.end());
	vector<ll> pv(p.size()), pw(p.size());
	for (int i = 1; i < p.size(); i++) {
		pv[i] = max(pv[i - 1], p[i].second);
		pw[i] = p[i].first;
	}
	ll ret = 0;
	for (int i = 0; i < 1 << rc; i++) {
		ll sv = 0, sw = 0;
		for (int j = 0; j < rc; j++) {
			if (i & (1 << j)) sv += v[j + lc], sw += w[j + lc];
		}
		if (sw > W) continue;
		int ptr = lower_bound(pw.begin(), pw.end(), W - sw + 1) - pw.begin() - 1;
		ret = max(ret, pv[ptr] + sv);
	}
	cout << ret << endl;
	return 0;
}