#include<fstream>
#define inf "rucsac.in"
#define outf "rucsac.out"
#define NMax 5100
#define GMax 10100
using namespace std;

fstream f(inf,ios::in), g(outf,ios::out);

int N, G;
int W[NMax], P[NMax];
int C[2][GMax], nl = 1, ol = 0;

void read()
{
	f>>N>>G;
	for(int i=1; i<=N; i++) f>>W[i]>>P[i];
}

void solve()
{
	for(int i=1; i<=N; i++)
	{
		for(int j=1; j<=G; j++)
		{
			C[nl][j] = C[ol][j];
			if( W[i]<=j && C[nl][j] <= C[ol][j-W[i]] + P[i] ) C[nl][j] = C[ol][j-W[i]] + P[i];
		}
		swap(nl, ol);
	}
	g<< C[ol][G];
}

int main()
{
	read(); solve();
	f.close(); g.close();
	return 0;
}