#include<fstream>
#include<algorithm>
using namespace std; 

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

int Profit[5001][10001];
int N, G;
int W[5001], P[5001];

int main()
{
	int i, j;
	
	in >> N >> G;
	for(i = 1; i <= N; i++)
		in >> W[i] >> P[i];
	
	for(i = 1; i <= N; i++)
		Profit[i][0] = 0;
	for(j = 1; j <= G; j++)
		Profit[0][j] = 0;
	
	for(i = 1; i <= N; i++)
		for(j = 1; j <= G; j++)
			if( W[i] <= j )
				Profit[i][j] = max( Profit[i-1][j-W[i]] + P[i], Profit[i-1][j] );
			else 
				Profit[i][j] = Profit[i-1][j];
			
			out << Profit[N][G]; 
			
	return 0;
}