#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;
}

Measured memory_bytes: 9224