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;

constexpr long long INF = (1LL << 60);

int main() {
	int n;
	long long max_w;
	cin >> n >> max_w;
	vector<long long> v(n), w(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i] >> w[i];
	}
	
	const int n1 = n / 2;
	const int n2 = n - n1;
	
	vector<pair<long long, long long>> dat;
	for (int s = 0; s < (1 << n1); s++) {
		long long value = 0, weight = 0;
		for (int i = 0; i < n1; i++) {
			if (s & (1 << i)) {
				value += v[i];
				weight += w[i];
			}
		}
		dat.emplace_back(weight, value);
	}
	
	sort(dat.begin(), dat.end(), [](pair<long long, long long> &l, pair<long long, long long> &r) {
		if (l.first == r.first) return (l.second > r.second);
		return (l.first < r.first);
	});
	
	for (int i = 0; i + 1 < dat.size(); i++) {
		pair<long long, long long> &s = dat[i];
		pair<long long, long long> &t = dat[i + 1];
		if (s.first <= t.first and s.second >= t.second) t = s;
	}

	long long ans = 0;
	for (int s = 0; s < (1 << n2); s++) {
		long long value = 0, weight = 0;
		for (int i = 0; i < n2; i++) {
			if (s & (1 << i)) {
				value += v[n1 + i];
				weight += w[n1 + i];
			}
		}
		if (weight <= max_w) {
			long long res = prev(lower_bound(dat.begin(), dat.end(), make_pair(max_w - weight, INF)))->second;
			ans = max(ans, res + value);
		}
	}
	
	cout << ans << '\n';
	
	return 0;
}
