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