#include <fstream>

using namespace std;

int n,D[2][10002],P[5002],W[5002],G;
 
ifstream f ("rucsac.in");
ofstream g  ("rucsac.out");

int max (int a,int b)
{
	return a>b ? a:b;
}

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