#include <fstream>
#include <iostream>

#define maximum(a,b) 	\
({						\
	typeof(a) _a = (a); \
	typeof(b) _b = (b);	\
	_a>=_b?_a:_b;		\
})

#define MAXN	5010
#define MAXG	10010

using namespace std;

short W[MAXN], P[MAXN];

int D[2][MAXG];

int main()
{
	int N, G;
	int which = 0;
	fstream fin("rucsac.in", fstream::in);
	fstream fout("rucsac.out", fstream::out);
	
	fin >> N >> G;
	//cout << N << " " << G << endl;
	
	for (int i=0; i<N; ++i)
	{
		fin >> W[i] >> P[i];
	}
	fin.close();
	
	for (int i=0; i<N; ++i)
	{
		for (int cw=0; cw<=G; ++cw)
		{
			D[!which][cw] = D[which][cw];
			
			if (W[i] <= cw)
				D[!which][cw] = maximum(D[!which][cw], D[which][cw - W[i]] + P[i]);
		}
		
		which = !which;
	}
	
	fout << D[which][G] << endl;
	
	fout.close();
	return 0;
}