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

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

int n, g;

int W[5005];
int P[5005];
int D[2][10005];

int main()
{
	fin >> n >> g;
	
	for( int i = 1; i <= n; ++i )
		fin >> W[i] >> P[i];	
	
	int l = 0;
	
	for( int i = 1; i <= n; ++i )
	{
		for( int cw = 1; cw <= g; ++cw )
		{
			if( W[l] <= cw )
				D[1 - l][cw] = max( D[l][cw], D[l][cw - W[i]] + P[i] );
			else
				D[l][cw] = D[1 - l][cw];
		}
		l = 1 - l;			
	}
	
	fout << D[l][g];
	
	return 0;
}