#include<cstdio>
#include<algorithm>

using namespace std;

#define MAXN 5010
#define MAXG 10010

int g,n,pmax;
int P[MAXN],W[MAXN];
int D[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 = g;cw>=1;cw--)
		{
			if (W[i] <= cw)
				D[cw] = max(D[cw],D[cw - W[i]] + P[i]);
		}
	
	pmax = D[g];
	f = fopen("rucsac.out","w");
	fprintf(f,"%i",pmax);
	fclose(f);
	
	return 0;
}