#include <fstream>
#include <iostream>
#include <algorithm>

std::ifstream f("rucsac.in");
std::ofstream g("rucsac.out");

int matrix[5001][10001];
int cost[5001];
int benefit[5001];
int N,G;

void read(){
	f >> N >> G;
	for(int i = 1; i <= N ;++i){
		f >> cost[i] >> benefit[i];
	}
}

void calculate(){
	for(int k = 1 ; k <= N ; ++k){
		for(int w = 1 ; w <= G ; ++w){
			if(cost[k] > w){
				matrix[k][w] = matrix[k - 1][w];
			}else{

				matrix[k][w] = std::max(matrix[k - 1][w],matrix[k - 1][w - cost[k]] + benefit[k]);
			}
		}
	}

}

int main(){
	read();
	calculate();
	g<< matrix[N][G];

	f.close();
	g.close();
	return 0;
	
}