#include<stdio.h>
#include<string.h>
int d[3][10010],g[5010],w[5010];
inline int max (int a, int b)
{
	if(a>b)	return a;
	return b;
}

int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	int i,n,j,G,la,lc;
	scanf("%d%d",&n,&G);
	for(i=1;i<=n;i++)
		scanf("%d%d",&g[i],&w[i]);
	for(i=1;i<=n;i++)
		for(j=1;j<=G;j++)
			{
				la=(i+1)%2;
				lc=i%2;
				if(g[i]>j)
					d[lc][j]=d[la][j];
				if(g[i]<=j)
					d[lc][j]=max(d[la][j],d[la][j-g[i]]+w[i]);
			}
	printf("%d\n",d[lc][G]);
	return 0;
}