#include <cstdio>

int n , D[2][10002], P[5002] , W[5002]  , G;

static inline int max(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,&G);
	for(int i=1;i<=n;++i)
		scanf("%d %d",&W[i],&P[i]);

	int l = 0;
	for(int i=1;i<=n;++i,l = 1-l)
		for(int j=0;j<=G;++j)
		{
			D[1-l][j] = D[l][j];

			if(W[i]<=j)
				D[1-l][j] = max(D[1-l][j],D[l][j-W[i]] + P[i]);
		}

	printf("%d\n",D[l][G]);
	return 0;
}