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 "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL N, W, w[112], v[112];
std::vector<std::pair<LL, LL>>wv;
std::vector<std::pair<LL, LL>>A, B;
LL ans;

int main()
{
	in >> N >> W;
	wv.resize(N);
	rep(i, N)
	{
		in >> v[i] >> w[i];
		wv[i].first = v[i], wv[i].second = w[i];
	}
	auto x = N / 2, y = N - N / 2;
	A.resize(1 << x); B.resize(1 << y);
	rep(i, (1 << x))
	{
		rep(j, x)
		{
			if (i&(1 << j))
			{
				A[i].first += wv[j].second;
				A[i].second += wv[j].first;
			}
		}
	}
	std::sort(A.begin(), A.end());
	for (LL i = 1; i < (1 << x); ++i) { A[i].second = std::max(A[i].second, A[i - 1].second); }
	rep(i, (1 << y))
	{
		rep(j, y)
		{
			if (i&(1 << j))
			{
				B[i].first += wv[x + j].second;
				B[i].second += wv[x + j].first;
			}
		}
	}
	for (auto b : B)
	{
		auto iter = std::upper_bound(A.begin(), A.end(), std::pair<LL, LL>(W - b.first, 1000000000000000ll));
		if (iter != A.begin()) { ans = std::max(ans, b.second + (iter - 1)->second); }
	}

	out << ans << std::endl;
	return 0;
}