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 <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))

int n;
i64 MAX;

i64 v[41];
i64 w[41];

int main()
{
	cin >> n >> MAX;
	int sz = n / 2;
	for(int i = 0;i < sz;i++)
		cin >> v[i] >> w[i];
	map<i64,i64> mp;
	mp[0] = 0;
	for(int i = 1;i < (1 << (sz));i++)
	{
		i64 we = 0;
		i64 val = 0;
		for(int j = 0;j < sz;j++)
		{
			if(i & (1 << j))
			{
				we += w[j];
				val += v[j];
			}
		}
		mp[we] = max(mp[we] , val);
	}

	auto ite = mp.begin();
	++ite;
	auto before = mp.begin();

	while(ite != mp.end())
	{
		(*ite).second = max((*ite).second , (*before).second);
		before = ite;
		++ite;
	}


	for(int i = sz;i < n;i++)
	{
		cin >> v[i - sz] >> w[i - sz];
	}
	
	sz = n - sz;


	i64 result = 0;
	for(int i = 0;i < (1 << sz);i++)
	{
		i64 we = 0;
		i64 val = 0;
		for(int j = 0;j < sz;j++)
		{
			if(i & (1 << j))
			{
				we += w[j];
				val += v[j];
			}
		}
		auto ite = mp.lower_bound(MAX - we + 1);
		if(ite == mp.begin()) continue;
		--ite;
		if((*ite).first + we <= MAX)
		{
			result = max(result , val + (*ite).second);
		}
	}

	cout << result << endl;
}

