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;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(a) a.begin(),a.end()
typedef long long ll;

using P = pair<ll,ll>;
#define v first
#define w second

// v高い順（vが同じならw軽い方優先）
bool comp(P a, P b){
    return a.v == b.v ? a.w < b.w : a.v > b.v;
}

int main(void){
    ll N,W;
    cin>>N>>W;
    vector<P> a(N);
    rep(i,N){
        ll v,w;
        cin>>v>>w;
        a[i] = {v,w};
    }
    vector<P> dp = {{0,0}};

    rep(i,N){
        vector<P> tmp;
        for(auto& s : dp){
            tmp.push_back(s);
            tmp.push_back({s.v + a[i].v, s.w + a[i].w});
        }

        sort(all(tmp),comp);
        dp.clear();
        ll w_border = W+1;
        for(auto& s : tmp){
            if( w_border > s.w){
                w_border = s.w;
                dp.push_back(s);
            }
        }
    }
    cout<<dp[0].v<<endl;
    return 0;
}

