#include<fstream>
#define NMAX 5010
#define GMAX 10010
using namespace std;

int N, G;
int W[NMAX], P[NMAX];
int d[2][GMAX];

void Read()
{
	ifstream fin("rucsac.in");
	fin >> N >> G;
	for(int i=1; i<=N; i++)
		fin >> W[i] >> P[i];
	fin.close();
}

inline int Max(int x, int y)
{
	return (x >= y) ? x : y;
}
void Solve()
{
	int linie = 0;
	for(int i=1; i<=N; i++)
	{
		for(int cw = 0; cw <= G; cw++)
		{
			d[1 - linie][cw] = d[linie][cw];
			
			if(W[i] <= cw)
			{
				int p = cw - W[i];
				d[1-linie][cw] = Max(d[linie][cw], P[i] + d[linie][p]);
			}
		}
		linie = 1 - linie;
	}
	
	ofstream fout("rucsac.out");
	fout << d[linie][G] << "\n";
	fout.close();
}

int main ()
{
	Read();
	Solve();
	return 0;
}