#include<fstream>
#include<cstdio>

using namespace std;

const int MaxN = 5001;
const int MaxG = 10001;

const char InFile[] = "rucsac.in";
const char OutFile[] = "rucsac.out";

int N,G,Sol,W[MaxN],P[MaxN],Din[MaxG];

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> G;
	int i,j;
	for( i = 1 ; i <= N ; ++i )
		fin >> W[i] >> P[i];
	Sol = 0;
	Din[0] = 0;
	for( i = 1 ; i <= N ; ++i )
		for( j = G - W[i] ; j >= 0 ; --j )
			if( Din[j+W[i]] < Din[j] + P[i] )
				{
					Din[j+W[i]] = Din[j] + P[i];
					if( Sol < Din[j+W[i]] )
						Sol = Din[j+W[i]];
				}
	fout << Sol << '\n';
	fin.close();
	fout.close();
	return 0;
}