#include<cstdio>
using namespace std;
int n,g,p[5001],w[5001],gr[10001],prof,gm;
int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d %d\n",&n,&g);
	for(int i=1;i<=n;i++) scanf("%d %d\n",&w[i],&p[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=gm;j>=0;j--)
			if(j+w[i]<=g)
			{
				if(gr[j+w[i]]<gr[j]+p[i])
				{
					gr[j+w[i]]=gr[j]+p[i];
					if(j+w[i]>gm) gm=j+w[i];
				}
			}
	}
	for(int i=0;i<=g;i++)
		if(prof<gr[i]) prof=gr[i];
	printf("%d\n",prof);
	fclose(stdin);fclose(stdout);
	return 0;
	
}