#include<stdio.h>
int n,i,j,w,d[2][1013],max;
struct obj
{
	int p,w;
}v[5013];
inline int mx(int a, int b)
{
	return(a>b?a:b);
}
int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&n,&w);
	for(i=1;i<=n;++i)
		scanf("%d%d",&v[i].w,&v[i].p),d[0][i]=0;
	max=-1;
	for(int k=1;k<=n;++k)
	{
		for(i=0;i<v[k].w;++i)d[1][i]=d[0][i];
		for(i=v[k].w;i<=w;++i)
			d[1][i]=mx(d[0][i],d[0][i-v[k].w]+v[k].p);
		for(i=0;i<=w;++i)
		{
			d[0][i]=d[1][i];
			if(max<d[1][i])max=d[1][i];
		}
	}
	printf("%d\n",max);
	return 0;
}