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 int long long
#define N 41
using namespace std;
typedef pair<int,int> P;


int Max(int &a,int b){return a=max(a,b);}

P calc(int bit,int a,int v[],int w[]){
  int rv=0,rw=0;
  for(int i=0;i<a;i++) if(bit>>i&1) rv+=v[i],rw+=w[i];
  return P(rw,rv); 
}

signed main(){
  int n,W;
  int v[N],w[N];
  cin>>n>>W;

  for(int i=0;i<n;i++) cin>>v[i]>>w[i];
  
  int a = n/2;
  int b = n - a;
  map<int,int> A;
  A[0] = 0;

  for(int i=0;i<(1<<a);i++){
    P p = calc(i,a,v,w);
    Max(A[p.first],p.second);
  }

  int mxv = 0;
  for(auto &p:A) p.second = Max(mxv,p.second);

  int ans = 0;
  for(int i=0;i<(1<<b);i++){
    P p = calc(i,b,v+a,w+a);
    int w=p.first,v = p.second;
    if(w>W)continue;
    auto it = --A.upper_bound(W-w);
    int av = it->second;
    Max(ans,v+av);
  }
  cout<<ans<<endl;
  return 0;
}