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<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
#define int long long
const int inf = 999999999999999999;
typedef long long ll;
typedef long double ld;
struct A {
	int w, v;
};
bool operator<(A a, A b) {
	if (a.w != b.w) return a.w < b.w;
	return a.v > b.v;
}
A a[40], b[2][1100000];
int n, w, sum[2];
void solve(int i, int v, int w, int end, int c) {
	if (i == end) {
		b[c][sum[c]] = A{ w,v };
		sum[c]++;
		return;
	}
	solve(i + 1, v + a[i].v, w + a[i].w, end, c);
	solve(i + 1, v, w, end, c);
}
signed main() {
	cin >> n >> w;
	for (int i = 0; i < n; i++)
		cin >> a[i].v >> a[i].w;
	solve(0, 0, 0, n / 2, 0);
	solve(n / 2, 0, 0, n, 1);
	sort(b[0], b[0] + sum[0]);
	sort(b[1], b[1] + sum[1]);
	int r = -1, y = sum[0];
	for (int i = 0; i < sum[0]; i++) {
		if (r >= b[0][i].v) {
			b[0][i].w = inf;
			y--;
		}
		else
			r = b[0][i].v;
	}
	sort(b[0], b[0] + sum[0]);
	int ans = 0;
	for (int i = 0; i < sum[1]; i++) {
		int k = lower_bound(b[0], b[0] + y, A{ w - b[1][i].w,0 }) - b[0];
		if (k > 0) k--;
		if (b[0][k].w + b[1][i].w <= w) 
			ans = max(ans, b[0][k].v + b[1][i].v);
	}
	cout << ans << endl;
	getchar(); getchar();
}