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 _USE_MATH_DEFINES
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

//#define int long long
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int n;
ll W;
ll w[50], v[50];
pll ps[1 << 20];

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n >> W;
	rep(i, 0, n)cin >> v[i] >> w[i];

	int n1 = n / 2;
	rep(i, 0, 1 << n1)
	{
		ll tw = 0, tv = 0;
		rep(j, 0, n1)
		{
			if (i & (1 << j))
			{
				tw += w[j];
				tv += v[j];
			}
		}
		ps[i] = mp(tw, tv);
	}
	
	sort(ps, ps + (1 << n1));
	
	int m = 1;
	rep(i, 1, 1 << n1)
	{
		if (ps[m - 1].second < ps[i].second)
		{
			ps[m++] = ps[i];
		}
	}
	
	ll ans = 0;
	rep(i, 0, 1 << (n - n1))
	{
		ll tw = 0, tv = 0;
		rep(j, 0, n - n1)
		{
			if (i & (1 << j))
			{
				tw += w[j + n1];
				tv += v[j + n1];
			}
		}
		if (tw <= W)
		{
			ll ttv = (lower_bound(ps, ps + m, mp(W - tw, 0x3f3f3f3f3f3f3f3fLL)) - 1)->second;
			chmax(ans, ttv + tv);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}
