#include<fstream>

using namespace std;
 ifstream f("rucsac.in");
 ofstream g("rucsac.out");
int w[5001], p[10001],optim[10001],n,G,i,j,sol;


int main()
 {

    f>>n>>G;
	for(i=1;i<=n;i++)
        f>>w[i]>>p[i];

	optim[0] = 0;


	for( i = 1; i <= n; ++i)
		for( j = G - w[i]; j >= 0; j--)
		{
			if( optim[j+w[i]] < optim[j] + p[i] )
			{
				optim[j+w[i]] = optim[j] + p[i];
				if( optim[j+w[i]] > sol)
					sol = optim[j+w[i]];
			}
		}
	g<<sol;
	return 0;
}