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

// Constante
const int sz = 5001;
const int wsz = (int)1e4+1;

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

int num, maxW; // Numarul de obiecte si greutatea maxima
int cost[sz], weight[sz];

int line1[wsz], line2[wsz];
int *current=line2, *previous=line1; // Linia curenta si linia precedenta

// Main
int main()
{
	in >> num >> maxW;
	
	for(int i=1 ; i<=num ; ++i)
		in >> weight[i] >> cost[i];
	
	
	// La fiecare pas, current[j] va fi profitul maxim pe care-l pot obtine folosind doar obiectele [1..i]
	// si un rucsac in care incape maxim greutatea j. previous[j] nu contine obiectul i
	for(int i=1 ; i<=num ; ++i)
	{
		swap(current, previous);
		
		// Atat timp cat obiectul curent e mai greu decat maximul rucsacului folosit, sunt sigur ca nu-l pot pune
		for(int j=1 ; j<weight[i] ; ++j)
			current[j] = previous[j];
		
		// Daca obiectul poate fi inclus in rucsacul de greutate j, il voi lua in rucsac doar daca cu el as avea
		// un profit mai mare decat am avut, la aceeasi greutate, fara el
		for(int j=weight[i] ; j<=maxW ; ++j)
			current[j] = max(previous[j], previous[j-weight[i]]+cost[i]);
	}
	
	// Raspunsul va fi pe pozitie de greutate maxima a ultimului element
	// avand intervalul [1..num] cu rucsac de greutate maxW
	out << current[maxW] << '\n';
	
	
	in.close();
	out.close();
	return 0;
}