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

// Constante
const int sz = 5001;

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

int elements, maxWeight;
int weight[sz], cost[sz];

vector<int> current, previous;

// Main
int main()
{	
	in >> elements >> maxWeight;
	for(int i=1 ; i<=elements ; ++i)
		in >> weight[i] >> cost[i];
	previous.resize(maxWeight+1);
	current.resize(maxWeight+1);
	
	for(int i=1 ; i<=elements ; ++i)
	{
		for(int j=0 ; j<=maxWeight ; ++j)
		{
			current[j] = previous[j];
			if(weight[i] <= j)
				current[j] = max(current[j], previous[j-weight[i]] + cost[i]);
		}
		current.swap(previous);
	}
	
	out << previous[maxWeight];
	
	in.close();
	out.close();
	return 0;
}