#include <stdio.h>
FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");
long sum[5001],v[5001][3],n,aux,nr,i,j,x,y,gr;
int main()
{
	fscanf(f,"%ld%ld",&n,&gr);
	for (i=0;i<n;i++)
	{
		fscanf(f,"%ld%ld",&v[i][1],&v[i][2]);
		for (j=gr-v[i][1];j>=0;j--)
			if(sum[j+v[i][1]]<sum[j]+v[i][2])
			{
				sum[j+v[i][1]]=sum[j]+v[i][2];
				if (sum[j+v[i][1]]>nr)
					nr=sum[j+v[i][1]];
			}
		//ef[i]=v[i][2]/v[i][1];
	}
	fprintf(g,"%ld",nr);
	/*for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++)
		{
			if (ef[i]<ef[j])
			{
				aux=ef[i];
				ef[i]=ef[i];
				ef[j]=aux;
				
				aux=v[i][1];
				v[i][1]=v[j][1];
				v[j][1]=aux;
				
				aux=v[i][2];
				v[i][2]=v[j][2];
				v[j][2]=aux;
			}
			else if (ef[i]==ef[j] && v[i][2]<v[j][2])
			{
				aux=ef[i];
				ef[i]=ef[i];
				ef[j]=aux;
				
				aux=v[i][1];
				v[i][1]=v[j][1];
				v[j][1]=aux;
				
				aux=v[i][2];
				v[i][2]=v[j][2];
				v[j][2]=aux;
			}
		}
	for (i=1;i<=n;i++)
	{
		if (v[i][1]<=gr)
		{
			gr=gr-v[i][1];
			nr=nr+v[i][2];
			x=v[i][1];
			y=v[i][2];
		}
		else if (v[i][1]<=gr+x && y<v[i][2])
		{
			gr=gr+x-v[i][1];
			nr=nr-y+v[i][2];
			x=v[i][1];
			y=v[i][2];
		}
	}
	fprintf(g,"%ld",nr);*/
	fclose(f);
	return 0;
}