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