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<cstdio>
                                        #include<vector>
                                        #include<queue>
                                        #include<map>
                                        #include<cstring>
                                        #include<string>
                                        #include <math.h>
                                        #include<algorithm>
                                    //    #include <boost/multiprecision/cpp_int.hpp>
                                        #include<functional>
                                #define int long long
                                        #define inf  1000000007
                                        #define pa pair<int,int>
                                        #define ll long long
                                        #define pal pair<double,pa>
                                        #define ppa pair<int,int>
                                        #define ppap pair<pa,pa>
                                        #define ssa pair<string,int>
                                        #define  mp make_pair
                                        #define  pb push_back
                                        #define EPS (1e-10)
                                        #define equals(a,b) (fabs((a)-(b))<EPS)
                                  #define VI vector<int>
                                        using namespace std;
                                        
                                  class pas{
                                    	public:
                                    	int x,y;
                                    	pas(int x=0,int y=0):x(x),y(y) {}
                                    	pas operator + (pas p) {return pas(x+p.x,y+p.y);}
                                    	pas operator - (pas p) {return pas(x-p.x,y-p.y);}
                                    	pas operator * (int a) {return pas(x*a,y*a);}
                                    	pas operator / (int a) {return pas(x/a,y/a);}
                                    //	double absv() {return sqrt(norm());}
                                    	int norm() {return x*x+y*y;}
                                    	bool operator < (const pas &p) const{
                                    		return x != p.x ? x<p.x: y<p.y;
                                    	}
                                    	bool operator == (const pas &p) const{
                                    		return x==p.x && y==p.y;
                                    	}
                                    };
int n,W;
vector<pas> ve1,ve2;

int v[50],w[50];
           signed main(){
      cin>>n>>W;
          
           	int n1=n/2;
           	int n2=n-n1;
           	
           	for(int i=0;i<n;i++)cin>>v[i]>>w[i];
           	for(int i=0;i<(1<<n1);i++){
           		int v1=0,w1=0;
           		for(int j=0;j<n1;j++)if(i&(1<<j)){
           			v1+=v[j];
           			w1+=w[j];
           		}
           		pas z={w1,v1};
           		ve1.pb(z);
           		//cout<<w1<<" "<<v1<<endl;
           	}
           	
           		
           	
           	for(int i=0;i<(1<<n2);i++){
           		int v1=0,w1=0;
           		for(int j=0;j<n2;j++)if(i&(1<<j)){
           			v1+=v[j+n1];
           			w1+=w[j+n1];
           		}
           			ve2.pb({w1,v1});
         //  		cout<<w1<<" "<<v1<<endl;
           	}
           	sort(ve1.begin(),ve1.end());
           	
           	sort(ve2.begin(),ve2.end());
           	int ans=0;
           	int d=0;
           	for(int i=0;i<ve2.size();i++){
           		ve2[i].y=max(d,ve2[i].y);
           		d=ve2[i].y;
           	}
           	for(auto v:ve1){
           		if(v.x>W) continue;
        //   		cout<<v.x<<endl;
           			int r=lower_bound(ve2.begin(),ve2.end(),(pas){1+W-v.x,-100})-ve2.begin();
           		r--;
           		ans=max(ans,v.y+ve2[r].y);
          // 		cout<<r<<" " <<v.y<<" "<<ve2[r].y<<endl;
           	}
           	cout<<ans<<endl;
           }
             