// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



struct Item{

	int v,w;

	int idx;	

};

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;

		}

	}

	Knapsack knapSackDP(int scale) const{

		Knapsack res = *this;

		int maximumValue = -INF;

		for( auto i : res.items ){

			maximumValue = max(maximumValue,i.v);

		}



		double rate = min(1.0,1.*scale/maximumValue);

		for( auto &i : res.items ){

			i.v = (int)(ceil(rate*i.v)+1e-9);

		}

		

		vector<int> dp(scale+1,INF);

		vector<vector<int>> lastId(scale+1);

		dp[0] = 0;

		for(int i = 0 ; i < res.items.size() ; i++){

			if( res.used[i] ) continue;

			for(int j = scale ; j >= res.items[i].v ; j--){

				if( dp[j-res.items[i].v] + res.items[i].w < dp[j] ){

					dp[j] = dp[j-res.items[i].v] + res.items[i].w;

					lastId[j].push_back(i);

				}

			}

		}

		int pr = INF;

		for(int i = scale ; i >= 0 ; i--){

			if( dp[i] <= maximumWeight - totalWeight ){

				int cur = i;

				while(cur > 0){

					int p = lastId[cur][lower_bound(lastId[cur].begin(),lastId[cur].end(),pr) - lastId[cur].begin() - 1];

					res.putItem(res.items[p]);

					cur -= res.items[p].v;

					pr = p;

				}

				break;

			}

		}

		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;

	}

};









int main(){

	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.knapSackDP(100000);

	cout << knap.totalValue << endl;

}

// Faster C++ solution for the same problem (measured speedup: 4.7044499115806415x):
#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;

}