// 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.742927587186688x):
#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(const Knapsack &original) const{

		int scale = 0;

		for( auto &i : items ){

			scale += i.v;

		}

		vector<DPInfo> dp(scale+1,{INF,INF,{}});

		dp[0] = {0,0,{}};

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

			if( used[i] ) continue;

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

				DPInfo nextV;

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

				nextV.trueValue = dp[j-items[i].v].trueValue + original.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 &original) const{

		int pr = INF;

		Knapsack res = *this;

		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(items[p]); // res.items[p]????????????

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

			pr = p;

		}

		return res;

	}



	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);

		for( auto &i : res.items ){

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

		}

		auto dp = res.makeDPtable(*this);



		int pr = INF;

		for(int i = dp.size()-1 ; i >= 0 ; i--){

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

				return recover(i,dp,*this);

			}

		}

	}

	Knapsack BigSmallDP(int valueThreshold) const{

		auto tmp = devideItems(valueThreshold);

		



	}

	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;

	//}

};









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(1000).localImprovement();

	cout << knap.totalValue << endl;

}