#include<stdio.h>
FILE *f,*gu;
int cmax[10002],uz[10002][5006];
int main()
{
	f=fopen("rucsac.in","r");
	gu=fopen("rucsac.out","w");
	int n,gmax,g[5003],c[5003],h;
	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]);
	cmax[0]=0;
	for(i=1;i<=gmax;++i)
	{
		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;
					}
				}
			}
		}
		uz[i][h]=1;
		for(j=0;j<n;j++)
		{
			if(uz[i][j]!=1)
				uz[i][j]=uz[i-g[h]][j];
		}
	}
	
	fprintf(gu,"%d\n",cmax[gmax]);
	/*for(i=0;i<n;i++)
		if(uz[cmax[gmax]][i]==1)
			fprintf(*/
	fclose(f);
	fclose(gu);
}