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 <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<long long>;
using pll = pair<long long, long long>;
#define rep(i,n) for(long long i(0);(i)<(n);(i)++)
ll INF = 1LL << 60;

void solve(ll N, ll W, vll v, vll w){
    //* complete search on the first half and record
    ll N2 = N/2;
    vector<pll> rec;
    rep(S, 1<<N2){
        ll sw=0, sv=0;
        rep(j, N2){
            if((S >> j) & 1 ) { //* Set S has 1 in j-th position from right
                sw += w[j];
                sv += v[j];
            }
        }
        rec.push_back(pll(sw, sv));
    }
    //* remove to make sure w <= w'  <==>  v <= v'
    sort(rec.begin(), rec.end());
    ll m=1;
    for(ll S=1; S < 1<<N2; S++){
        if(rec[m-1].second < rec[S].second){
            rec[m] = rec[S];
            m++;
        }
    }
    //* complete search for the rest half
    ll res = 0;
    rep(S, 1<<(N-N2)){
        ll sw = 0, sv=0;
        rep(j, N-N2){
            if(S >> j & 1){
                sw += w[N2+j];
                sv += v[N2+j];
            }
        }
        if(sw <= W){
            ll tv = (lower_bound(rec.begin(), rec.begin()+m, make_pair(W-sw, INF))-1) ->second;
            res = max(res, sv + tv);
        }
    }
    cout << res << endl;


}

int main(){
    ll N, W;
    cin >> N >> W;
    vll v(N), w(N);
    rep(i, N){
        scanf("%lld", &v[i]);
        scanf("%lld", &w[i]);
    }
    solve(N, W, move(v), move(w));
    return 0;
}
