#include<fstream>

#define maxn 5001
#define maxg 10001

using namespace std;
ofstream out("rucsac.out");

int n , G , g[maxn] , c[maxn];

int bst[maxn][maxg];

void read();
void rucsac();

int main()
{
	read();
	rucsac();
	out << bst[n][G];
	return 0;
}

void read()
{
	ifstream in("rucsac.in");
	in >> n >> G;
	for ( int i = 1 ;i<=n;i++)
		in >> g[i] >> c[i];
}

void rucsac()
{
	for( int i=1 ;i<=n;i++)
		for ( int j=1; j<=G;j++)
		{
			
			if(g[i] <=j )
				bst[i][j] = max ( bst[i-1][j] , bst[ i-1 ][ j-g[i] ] + c[i] );
			else
				bst[i][j] = bst[i-1][j];
		}
}