#include<stdio.h>
FILE *f,*gu;
int cmax[10000],uz[10000][5000],g[5000],c[5000];
int main()
{
	f=fopen("rucsac.in","r");
	
	int n,gmax,h,MAX=0,H=-1;
	fscanf(f,"%d%d",&n,&gmax);
	register int i,j,max;
	for(i=1;i<=gmax+1;i++)
		cmax[i]=-1;
	for(i=0;i<n;++i)
		fscanf(f,"%d%d",&g[i],&c[i]);
	fclose(f);
	cmax[0]=0;
	for(i=1;i<=gmax;++i)
	{
		h=-1;
		max=0;
		for(j=0;j<n;++j)
		{
			if(g[j]<=i && cmax[i-g[j]]!=-1)
			{
				if(uz[i-g[j]][j]!=1)
				{
					max=cmax[i-g[j]]+c[j];
					if(cmax[i]<max)
					{
						cmax[i]=max;
						h=j;
						if(MAX<cmax[i])
						{
							MAX=cmax[i];
							H=h;
						}
					}
				}
			}
		}
		if(h!=-1)
		{
			uz[i][h]=1;
			for(j=0;j<n;j++)
			{
				if(uz[i][j]!=1)
					uz[i][j]=uz[i-g[h]][j];
			}
		}
	}
	gu=fopen("rucsac.out","w");
	fprintf(gu,"%d\n",MAX);
	fclose(gu);
}