#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int> >castig(2);
vector<int>Gr,C;
int main()
{
	FILE *in=fopen("rucsac.in","r");
	int n,g,i,j,l;
	fscanf(in,"%d %d",&n,&g);
	Gr.resize(n+1);
	C.resize(n+1);
	for(i=0;i<2;++i)
		castig[i].resize(g+1);
	for(i=1;i<=n;++i)
	{
		//castig[i].resize(g+1);
		fscanf(in,"%d %d",&Gr[i],&C[i]);
	}
	fclose(in);
	for(i=1,l=1;i<=n;++i,l=1-l)
		for(j=1;j<=g;++j)
		{ if(l)
			if(j>=Gr[i])
				castig[l][j]=max( castig[l-1][j],castig[l-1][j-Gr[i]]+C[i] );
			else
				castig[l][j]=castig[l-1][j];
		  else	
			if(j>=Gr[i])
				castig[l][j]=max( castig[l+1][j],castig[l+1][j-Gr[i]]+C[i] );
			else
				castig[l][j]=castig[l+1][j];
		}
	FILE *out=fopen("rucsac.out","w");
	fprintf(out,"%d\n",castig[1][g]);	
	fclose(out);
	return 0;
}