#include <bits/stdc++.h>
using namespace std;

struct Item{
	int v,w;
	int idx;	
};

struct DPInfo{
	int weight,trueValue;
	vector<int> lastId;
	bool operator < (const DPInfo &op) const {
		return weight != op.weight ? weight < op.weight : trueValue > op.trueValue; // INVERSE!!
	}

};


const int INF = 1000000000;
class Knapsack{
public:

	int maximumWeight;
	vector<Item> items;
	Knapsack(int maximumWeight_,vector<Item> items_) : maximumWeight(maximumWeight_),items(items_) {
		used.resize(items.size(),false);
		totalWeight = totalValue = 0;
		sort(items.begin(),items.end(),[](Item a,Item b){ return a.v * b.w > b.v * a.w; });
	}
	int totalValue;
	int totalWeight;
	vector<bool> used;
	bool operator < (const Knapsack &op) const {
		if( totalValue == op.totalValue )
			return totalWeight > op.totalWeight;
		return totalValue < op.totalValue;
	}

	bool canPut(const Item &x){
		return !used[x.idx] && x.w <= maximumWeight - totalWeight;
	}
	bool putItem(const Item &x){
		if( canPut(x) ){
			totalWeight += x.w;
			totalValue += x.v;
			used[x.idx] = true;
			return true; // success
		}else{
			return false; // failure
		}
	}
	bool removeItem(const Item &x){
		if( used[x.idx] ){
			totalWeight -= x.w;
			totalValue -= x.v;
			used[x.idx] = false;
			return true;
		}
		return false;
	}
	int swapAtoB(Item x,Item y){
		if( used[x.idx] && !used[y.idx] ){
			if( totalWeight - x.w + y.w > maximumWeight ) return -INF;
			return y.v - x.v;
		}else{
			return -INF;
		}
	}
	//??¢??????????????\?????¨??????????????§????????????????????????
	pair<Knapsack,Knapsack> devideItems(int valueThreshold) const{
		Knapsack low = *this, high = *this;
		low.items.clear();
		high.items.clear();
		for(int i = 0 ; i < items.size() ; i++){
			if( items[i].v <= valueThreshold){
				low.items.push_back(items[i]);
			}else{
				high.items.push_back(items[i]);
			}
		}
		return {low,high};
	}

	vector<DPInfo> makeDPtable(int itemscale) const{
		if( items.size() == 0 ){
			return vector<DPInfo>(1,{0,0,{}});
		}
		Knapsack compressed = *this;
		int maximumValue = -INF;
		for( auto i : compressed.items ){
			maximumValue = max(maximumValue,i.v);
		}
		double rate = min(1.0,1.*itemscale/maximumValue);
		for( auto &i : compressed.items ){
			i.v = (int)(ceil(rate*i.v)+1e-9);
		}

		int scale = 0;
		for( auto &i : compressed.items ){
			scale += i.v;
		}
		vector<DPInfo> dp(scale+1,{INF,-INF,{}});
		dp[0] = {0,0,{}};
		for(int i = 0 ; i < compressed.items.size() ; i++){
			if( compressed.used[i] ) continue;
			for(int j = scale ; j >= compressed.items[i].v ; j--){
				DPInfo nextV;
				nextV.weight = dp[j-compressed.items[i].v].weight + compressed.items[i].w;
				nextV.trueValue = dp[j-compressed.items[i].v].trueValue + items[i].v;
				if( nextV < dp[j] ){
					dp[j].weight = nextV.weight;
					dp[j].trueValue = nextV.trueValue;
					dp[j].lastId.push_back(i);
				}
			}
		}
		return dp;
	}
	Knapsack recover(int cur,const vector<DPInfo> &dp,const Knapsack &originalBag,int itemscale) const{
		Knapsack compressed = originalBag;
		int maximumValue = -INF;
		for( auto i : compressed.items ){
			maximumValue = max(maximumValue,i.v);
		}
		double rate = min(1.0,1.*itemscale/maximumValue);
		for( auto &i : compressed.items ){
			i.v = (int)(ceil(rate*i.v)+1e-9);
		}

		int pr = INF;
		Knapsack res = *this;
		//cout << cur << "<<" << endl;
		while(cur > 0){
			int p = dp[cur].lastId[lower_bound(dp[cur].lastId.begin(),dp[cur].lastId.end(),pr) - dp[cur].lastId.begin() - 1];
			res.putItem(originalBag.items[p]); // res.items[p]????????????
			cur -= compressed.items[p].v;
			pr = p;
		}
		return res;
	}

	Knapsack BigSmallDP(int valueThreshold) const{
		auto tmp = devideItems(valueThreshold);
		auto dp1 = tmp.first.makeDPtable(valueThreshold);
		auto dp2 = tmp.second.makeDPtable(valueThreshold);
		vector< pair<int,int> > happySeq1;
		vector< pair<int,int> > happySeq2;

		int maximum = -1;
		for(int i = 0 ; i < dp1.size() ; i++){
			if( dp1[i].weight == INF ) continue;
			pair<int,int> key = {dp1[i].weight,maximum=max(maximum,dp1[i].trueValue)};
			auto &seq = happySeq1;
			while( seq.size() && seq.back().first >= key.first ) seq.pop_back();
			seq.push_back(key);
		}
		//for( auto p : happySeq1 ) cout << p.first << " " << p.second << endl;
		maximum = -1;
		for(int i = 0 ; i < dp2.size() ; i++){
			if( dp2[i].weight == INF ) continue;
			pair<int,int> key = {dp2[i].weight,maximum=max(maximum,dp2[i].trueValue)};
			auto &seq = happySeq2;
			while( seq.size() && seq.back().first >= key.first ) seq.pop_back();
			seq.push_back(key);
		}
		
		int limit = maximumWeight - totalWeight;
		int j = happySeq2.size() - 1;
		pair<int,pair<int,int>> maximumPair = {-1,{-1,-1}};

		for(int i = 0 ; i < happySeq1.size() ; i++){
			while( j &&happySeq2[j].first > limit - happySeq1[i].first ) j--;
			// cerr << happySeq1[i].second<< "(" << happySeq1[i].first << ") ";
			 // cerr <<  happySeq2[j].second << "(" << happySeq2[j].first << ")" << " " << maximumWeight << endl;
			
			if( happySeq2[j].first + happySeq1[i].first <=  limit) 
				maximumPair = max(maximumPair,{happySeq1[i].second+happySeq2[j].second,{happySeq1[i].first,happySeq2[j].first}});
		}
		//cerr << maximumPair.first << "|" << maximumPair.second.first << "|" << maximumPair.second.second << endl;
		 
		auto res = *this;
		auto func = [&](const vector<DPInfo> &dp,int limit,const Knapsack &compressedBag,int valueThreshold){
			for(int i = dp.size() - 1 ; i >= 0 ; i--){
				if( dp[i].weight <= limit ){
					res = res.recover(i,dp,compressedBag,valueThreshold);
					return;
				}

			}
		};
		// for( auto p : tmp.first.items ){
			// cout << p.v << " " << p.w << " " << p.idx << "<" << endl;
		// }
		// cerr << "==" << maximumPair.second.first << "==" << endl;
		// cerr << "==" << maximumPair.second.second << "==" << endl;
		func(dp1,maximumPair.second.first,tmp.first,valueThreshold);
		func(dp2,maximumPair.second.second,tmp.second,valueThreshold);
		// cerr << maximumPair.first << " -> " << res.totalValue << "/" << valueThreshold << endl;
		return res;



	}
	Knapsack localImprovement() const{
		Knapsack res = *this;
		for(int i = 0 ; i < res.items.size() ; i++){	
			res.putItem(res.items[i]);
		}
		return res;
	}
//	Knapsack localImprovement() const{
//		Knapsack res = *this;

		//while(true){
			// ????¬??????????????????????????????§??????????
			//for(int i = 0 ; i < res.items.size() ; i++){	
			//	res.putItem(res.items[i]);
			//}
			// auto reflesh = [&](){
				// for(int i = 0 ; i < res.items.size() ; i++){
					// if( res.used[i] ){

						// auto tmp = res;
						// tmp.removeItem(tmp.items[i]);
						// for(int j = 0 ; j < tmp.items.size() ; j++){
							// if( i != j && !tmp.used[j] ){	
								// tmp.putItem(tmp.items[j]);
							// }
						// }
						// if( res < tmp ){
							// res = tmp;
							// return true;
						// }
					// }
				// }
				// return false;
			// };
			// if( reflesh() ) continue;
			
			// auto reflesh2 = [&](){
				// for(int i = 0 ; i < res.items.size() ; i++){
					// if( res.used[i] ){

						// for(int j = 0 ; j < res.items.size() ; j++){
							// if( !res.used[j] ){
								// if( res.swapAtoB(res.items[i],res.items[j]) >= 0 ){
									// res.removeItem(res.items[i]);
									// res.putItem(res.items[j]);
									// return true;
								// }
							// }
						// }
					// }
				// }
				// return false;
			// };
			// if( reflesh2() ) continue;
			//break;
		//}
		//return res;
	//}
};


pair<int,vector<Item>> makeTestcase(int size){
	vector<Item> res;
	for(int i = 0 ; i < size ; i++){
		res.push_back({rand()%10000+1,rand()%10000+1,i});
	}
	int n = rand() % 10000 * size;
	return {n,res};
}




int main(){
	// int trying = 10000;
	// int all = 0;
	// int suc = 0;
	// for(int i = 0 ; i < trying ; i++){
		// int n;
		// vector<Item> items;
		// tie(n,items) = makeTestcase(100);
		// Knapsack knap(n,items);
		// auto uso = knap.BigSmallDP(311).localImprovement();
		// auto tru = knap.BigSmallDP(1000).localImprovement();

		// if( tru.totalValue != uso.totalValue ){
			// cerr << tru.totalValue << " " << uso.totalValue << endl;
		// }
		
	// }
	int n,m;
	cin >> m >> n;
	vector<Item> items;
	
	for(int i = 0 ; i < m ; i++){
		int x,y;
		cin >> x >> y;
		items.push_back({x,y,i});
	}

	Knapsack knap(n,items);
	knap = knap.BigSmallDP(300).localImprovement();
	cout << knap.totalValue << endl;
}

Measured memory_bytes: 5036