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 "MyDisjointset.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <map>
#include <string.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll INF = 2000000000;
int main() {
	ll n, W; cin >> n >> W;
	ll *v = new ll[n], *w = new ll[n];
	for (int i = 0; i < n; i++)
		cin >> v[i] >> w[i];
	int h = n / 2;
	P *h1 = new P[1 << h];
	memset(h1, 0, sizeof(h1));
	for (int i = 0; i < (1 << h); i++)
		for (int j = 0; j < h; j++)
			if (i >> j & 1) { h1[i].second += v[j]; h1[i].first += w[j]; }
	sort(h1, h1 + (1 << h));
	int m = 0;
	for (int i = 1; i < (1 << h); i++) 
		if (h1[m].second < h1[i].second) 
			h1[++m] = h1[i];
	m++;
	int hr = n - n / 2;
	P *h2 = new P[1 << hr];
	memset(h2, 0, sizeof(h2));
	for (int i = 0; i < (1 << hr); i++)
		for (int j = 0; j < hr; j++)
			if (i >> j & 1) { h2[i].second += v[h + j]; h2[i].first += w[h + j]; }
	ll res = -1;
	for (int i = 0; i < (1 << hr); i++) {
		ll mw = W - h2[i].first;
		if (mw >= 0) {
			ll t = (lower_bound(h1, h1 + m, P(mw, INF)) - 1)->second;
			res = max(res, h2[i].second + t);
		}
	}
	cout << res << endl;
}