#include<fstream>

#define maxn 5001
#define maxg 10001

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

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

int bst[3][maxg];

void read();
void rucsac();

int main()
{
	read();
	rucsac();
	out << bst[1][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()
{
	int l = 0;
	//linia 0 este bst[i-1][j]
	//linia 1 este bst[i][j]
	for( int i=1 ;i<=n;i++, l = 1-l)
		for ( int j=1; j<=G;j++)
		{
			
			if(g[i] <=j )
				bst[ 1-l ][j] = max ( bst[ l ][j] , bst[ l ][ j-g[i] ] + c[i] );
			else
				bst[ 1-l ][j] = bst[ l ][j];
		}
}