#include <iostream>
#include <fstream>
#define nmax 5005
#define gmax 10005
using namespace std;

int curr[gmax], prev[gmax];
int N, G, profit[nmax], greutate[nmax];

int main() {
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	int i, j;
	
	f>>N>>G;
	
	for(i=1; i<=N; i++)
		f>>greutate[i]>>profit[i];
	
	for(j=1; j<=G; j++)
		curr[j] = 0, prev[j] = 0;
			
	prev[ greutate[1] ] = profit[1];
	
	for(i = 2; i <= N; i++) {
		for(j = 1; j <= G; j++) {
			curr[j] = prev[j];
			if(greutate[i] <= j) {
				curr[j] = max(curr[j], profit[i]);	//daca iau numai corpul i
				if(prev[j - greutate[i]] != 0) curr[j] = max(curr[j], prev[j - greutate[i]] + profit[i]);
				}
			}
		for(j = 1; j <= G; j++) prev[j] = curr[j];
	}
			
	int sol = 0;
	for(j=1; j<=G; j++) sol = max(sol, curr[j]);
	g<<sol<<"\n";
	
	return 0;
}