#include<cstdio>
#include<algorithm>

using namespace std;

#define MAXN 5010
#define MAXG 10010

int g,n,pmax;
int P[MAXN],W[MAXN];
int D[MAXN][MAXG];

int main()
{
	FILE*f;
	
	f = fopen("rucsac.in","r");
	fscanf(f,"%d%d",&n,&g);
	for (int i=1;i<=n;i++)
		fscanf(f,"%d %d",&W[i],&P[i]);
	
	fclose(f);
	
	for (int i=1;i<=n;i++)
		for (int cw = 0;cw<=g;cw++)
		{
			D[i][cw] = D[i-1][cw];
			if (W[i] <= cw)
				D[i][cw] = max(D[i-1][cw],D[i-1][cw - W[i]] + P[i]);
		}
	
	pmax = D[n][g];
	f = fopen("rucsac.out","w");
	fprintf(f,"%i",pmax);
	fclose(f);
	
	return 0;
}