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>

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line

int main()
{
	int N; cin >> N;
	ll W; cin >> W;
	vector<ll> v(N), w(N);
	rep(i,N) cin >> v[i] >> w[i];
	int N2 = N / 2;
	vector<pair<ll, ll>> P;
	// 前半 N2　個について、選ぶかどうかで全列挙 (2^N2)
	for (int i = 0; i < (1 << N2); i++) {
		ll sum_w = 0, sum_v = 0;
		for(int j = 0; j < N2; j++) {
			if ((i >> j) & 1) {
				// j番目のbitが経っている
				sum_w += w[j];
				sum_v += v[j];
			}
		}
		P.push_back(make_pair(sum_w, sum_v));
	}

	// 無駄な要素を取り除く
	// P[i].first <= P[j].firts かつ P[i].second >= P[j].secondとなる j は不要
	sort(P.begin(), P.end());

	int m = 1;
	for(int i = 1; i < (1 << N2); i++){
		// P[i].first <= P[j].first のとき P[i].second < P[j].secondとなるようにする
		if (P[m-1].second < P[i].second) { //この条件を満たすi を残す
			P[m] = P[i];
			m++;
		}
	}

	// 後半 N-N2 個について全列挙
	const ll INF = 1LL << 60;
	ll ans = 0;
	for (int i = 0; i < (1 << N - N2); i++){
		ll sum_w = 0, sum_v = 0;
		for (int j = 0; j < N - N2; j++) {
			if(( i >> j) & 1) {
				sum_w += w[N2 + j];
				sum_v += v[N2 + j];
			}
		}
		// P[idx].first <= W - sum_w を満たす最大のidxを求める
		if (sum_w <= W) {
			pair<ll, ll> tmp(W - sum_w, INF);
			// 範囲は [0, m)
			// idx = (W - sum_w を超える最初の要素の index) - 1
			int idx = lower_bound(P.begin(), P.begin() + m, tmp) - P.begin() - 1;
			ans = max(ans, sum_v + P[idx].second);
		}
	}
	cout << ans << endl;
}

