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

Measured memory_bytes: 8868