#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 5005
#define MAXG 10005

FILE *f = fopen ("rucsac.in","r");
FILE *g = fopen ("rucsac.out","w");

int N, G, PMAX;
int W[MAXN], P[MAXN], D[2][MAXG];

int main()
{
	fscanf (f, "%d%d", &N, &G);
	for (int i = 1; i <= N; i++)
		fscanf (f, "%d%d", &W[i], &P[i]);
	
	for (int i = 1; i <= N; i++)
		for (int cw = 0; cw <= G; cw++)
		{
			D[i % 2][cw] = D[1 - i % 2][cw];		// nu pun obiectul i
			
			if (W[i] <= cw)
				D[i % 2][cw] = max(D[i % 2][cw], D[1 - i % 2][cw - W[i] ] + P[i] );
		}
		
	PMAX = D[N % 2][G];
	
	fprintf (g, "%d\n", PMAX);
	
	fclose(f);
	fclose(g);
	
	return 0;
}