#include<cstdio>
using namespace std;

FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");


long N,G,gr[5001],p[5001],optim[10005];

long maxim;

int main()
{
	fscanf(f,"%ld%ld",&N,&G);
	for (int i=1;i<=N;i++)
	fscanf(f,"%ld%ld",&gr[i],&p[i]);
	
	int Gmax=0;
	
	for (int i=1;i<=N;i++)
	
		for (int j=Gmax;j>=0;j--)
			if ( optim[ j+gr[i] ] < optim[j]+p[i] && j+gr[i]<=G )
				{ optim[ j+gr[i] ]=optim[j]+p[i] ;
					
				  if (j+gr[i]>Gmax) Gmax=j+gr[i];
				  if (optim[j+gr[i]]>maxim) maxim=optim[j+gr[i]];
				}
				
				
	fprintf(g,"%ld\n",maxim);
	
	
return 0;}