// 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.746599468757739x):
#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 itemscale) const{

		Knapsack res = *this;

		int maximumValue = -INF;

		

		for( auto i : res.items ){

			maximumValue = max(maximumValue,i.v);

		}



		

		

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

		int scale = 0;

		for( auto &i : res.items ){

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

			scale += i.v;

		}

		

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

	cout << knap.totalValue << endl;

}