// Include
#include <fstream>
using namespace std;

// Constante
const int sz = 5001;
const int wsz = 10001;

// Variabile
ifstream in("rucsac.in");
ofstream out("rucsac.out");

int num, maxw;
int weight[sz], cost[sz];

int line1[wsz], line2[wsz];
int *current=line2, *previous=line1;

// Main
int main()
{
	in >> num >> maxw;
	for(int i=1 ; i<=num ; ++i)
		in >> weight[i] >> cost[i];
	
	for(int i=1 ; i<=num ; ++i)
	{
		swap(current, previous);
		for(int j=1 ; j<weight[i] ; ++j)
			current[j] = previous[j];
		
		for(int j=weight[i] ; j<=maxw ; ++j)
			current[j] = max(previous[j], previous[j-weight[i]] + cost[i]);
	}
	
	out << current[maxw] << '\n';
	
	in.close();
	out.close();
	return 0;
}