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>
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
*/

#define INF 10e15
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

int main(){
	long long int n, W;
    cin >> n >> W;

    long long int v, w;
    vector<pair<long long int, long long int> > a;

    long long int i, j;
    for(i = 0; i < n; i++){
        cin >> v >> w;
        pair<long long int, long long int> p = make_pair(w, v);
        a.push_back(p);
    }

    vector<pair<long long int, long long int> > x;
    for(i = 0; i < (1<<(n/2)); i++){
        long long int tmp_w = 0;
        long long int tmp_v = 0;
        for(j = 0; j < n/2; j++){
            if((i>>j)&1){
                tmp_w += a[j].first;
                tmp_v += a[j].second;
            }
        }
        pair<long long int, long long int> p = make_pair(tmp_w, tmp_v);
        x.push_back(p);
    }
    sort(x.begin(), x.end());

    for(i = 1; i < x.size(); i++){
        x[i].second = max(x[i].second, x[i-1].second);
    }


    long long int ans = 0;
    for(i = 0; i < (1<<(n - n/2)); i++){
        long long int tmp_w = 0;
        long long int tmp_v = 0;
        for(j = 0; j < n - n/2; j++){
            if((i>>j)&1){
                tmp_w += a[n/2+j].first;
                tmp_v += a[n/2+j].second;
            }
        }

        if(tmp_w <= W){
            long long int tmp;
            pair<long long int, long long int> p = make_pair(W-tmp_w, INF);
            tmp = (lower_bound(x.begin(), x.end(), p) - 1) -> second;
            ans = max(ans, tmp + tmp_v);
        }

    }

    cout << ans << endl;
}
