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 <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 2000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
int main() {
#define int long long
	long long n, w;
	cin >> n >> w;
	vector<pair<int,int>> nya;
	REP(i, n) {
		int a,b;
		cin >> a >> b;
		nya.push_back(make_pair(a,b));
	}
	while (nya.size() != 40) {
		nya.push_back(make_pair(0, 0));
	}
	vector<pair<int,int>> a, b;
	for (int i = 0;i < 1048576;++i) {
		int now = i;
		int volume = 0;
		int value = 0;
		for (int q = 0;now != 0;++q) {
			if (now % 2 == 1) {
				volume += nya[q].second;
				value += nya[q].first;
			}
			now /= 2;
		}
		a.push_back(make_pair(volume, value));
	}
	for (int i = 0;i < 1048576;++i) {
		int now = i;
		int volume = 0;
		int value = 0;
		for (int q = 20;now != 0;++q) {
			if (now % 2 == 1) {
				volume += nya[q].second;
				value += nya[q].first;
			}
			now /= 2;
		}
		b.push_back(make_pair(volume, value));
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int b_itr = b.size() - 1;
	for (int i = 1;i < a.size();++i) {
		a[i].second = max(a[i].second, a[i - 1].second);
		b[i].second = max(b[i].second, b[i - 1].second);
	}
	int ans = 0;
	for (int i = 0;i < a.size();++i) {
		while (b_itr >= 0&&a[i].first + b[b_itr].first > w) {
			b_itr--;
		}
		if (b_itr == -1) break;
		ans = max(ans, a[i].second + b[b_itr].second);
	}
	cout << ans << endl;
	return 0;
}
