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
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
//#include "MyMath.h"
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#include <math.h>
using namespace std;
const int num = 40, num1 = 10000000;
double numd = 10000000.0;
const int INF = 2000000000;
typedef long long int ll;
pair<ll, ll> l[1 << (num / 2)], r[1 << (num - num / 2)], a[num / 2], b[num / 2];
int main() {
	int n;
	ll W;
	cin >> n >> W;
	int m = n - n / 2;
	for (int i = 0; i < n / 2; i++)
		cin >> a[i].second >> a[i].first;
	//int k = 0;
	for (int i = 0; i < m; i++)
		/*cin >> b[k].second;
		cin >> b[k++].first;*///????????§k??????????????????
		cin >> b[i].second >> b[i].first;
	for (int i = 0; i < 1 << n / 2; i++) {
		ll v = 0, w = 0; 
		for(int j = 0; j < n / 2; j++)
			if (i >> j & 1) {
				v += a[j].second;
				w += a[j].first;
			}
		l[i] = make_pair(w, v);
	}
	for (int i = 0; i < 1 << m; i++) {
		ll v = 0, w = 0;
		for (int j = 0; j < m; j++)
			if (i >> j & 1) {
				v += b[j].second;
				w += b[j].first;
			}
		r[i] = make_pair(w, v);
	}
	sort(l, l + (1 << n / 2));
	sort(r, r + (1 << m));
	int s = 0;
	/*for (int i = 0; i < 1 << n / 2; i++)
		cout << l[i].first << " " << l[i].second << endl;
	for (int i = 0; i < 1 << m; i++)
		cout << r[i].first << " " << r[i].second << endl;*/
	for (int i = 1; i < 1 << n / 2; i++) 
		if (l[s].second < l[i].second) {
			l[++s] = l[i];
			//cout << "S" << endl;
		}
	int t = 0;
	for (int i = 1; i < 1 << m; i++)
		if (r[t].second < r[i].second) {
			r[++t] = r[i];
			//cout << "T" << endl;
		}
	//cout << "s" << s << "t" << t << endl;
	/*for (int i = 0; i <= s; i++)
		cout << l[i].first << " " << l[i].second << endl;
	for (int i = 0; i <= t; i++)
		cout << r[i].first << " " << r[i].second << endl;*/
	ll maxv = 0;
	/*for (int i = 0; i <= s; i++) {
		if (W < l[i].first) continue;
		ll w = W - l[i].first;
		cout << "i" << i << endl;	
		cout << "w" << w << endl;
		cout << "u" << upper_bound(r, r + t, make_pair(w, l[i].second))->second << endl;
		cout << "u" << upper_bound(r, r + t + 1, make_pair(w, l[i].second)) -> second << endl;
		cout << "u" << upper_bound(r, r + t + 2, make_pair(w, l[i].second))->second << endl;
		cout << "l" << lower_bound(r, r + t + 1, make_pair(w, l[i].second)) -> second << endl;
		cout << (upper_bound(r, r + t + 1, make_pair(w, l[i].second)) - 1)->second + l[i].second << endl;
		maxv = max(maxv, (lower_bound(r, r + t + 1, make_pair(w, l[i].second)) - 1)->second + l[i].second);
	}*/
	for (int i = 0; i <= t; i++) {
		if (W < r[i].first) continue;
		ll w = W - r[i].first;
		maxv = max(maxv, (lower_bound(l, l + s + 1, make_pair(w, r[i].second)) - 1)->second + r[i].second);
	}
	cout << maxv << endl;
	return 0;
}