#include <cstdio>

using namespace std;

long dyn[3][10010],g[5001],w[5001],la,lc,i,j,weight,n;

long maxim (long a, long b)
{
	if(a>b)
		return a;
	return b;
}

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