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

int dp[nmax][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(i=1; i<=N; i++)
		for(j=1; j<=G; j++)
			dp[i][j] = 0;
			
	dp[1][ greutate[1] ] = profit[1];
	
	for(i = 2; i <= N; i++) 
		for(j = 1; j <= G; j++) {
			dp[i][j] = dp[i-1][j];
			if(greutate[i] <= j) {
				dp[i][j] = max(dp[i][j], profit[i]);	//daca iau numai corpul i
				if(dp[i-1][j - greutate[i]] != 0) dp[i][j] = max(dp[i][j], dp[i-1][j - greutate[i]] + profit[i]);
				}
			}
			
	int sol = 0;
	for(j=1; j<=G; j++) sol = max(sol, dp[N][j]);
	g<<sol<<"\n";
	
	return 0;
}