#include <stdio.h>

#define NMAX 5000
#define GMAX 10000

int V[NMAX+1][GMAX+1];
int P[NMAX], W[NMAX];

int N, G;

#define MAX(a, b) (a) < (b) ? (b) : (a)

void dp(int N, int G)
{
	int i, j, t1, t2;
	
	for (j = 0; j <= G; j++)
		V[0][j] = 0;
	for (i = 1; i <= N; i++) 
		for (j = 0; j <=G; j++) {
			t1 = V[i-1][j];
			t2 = 0;
			if (j - W[i] >= 0) 
				t2 = P[i] + V[i-1][j-W[i]];
			V[i][j] = MAX(t1, t2);
		}		
}

void read_data(void)
{
	int i;
	
	fscanf(stdin, "%d %d", &N, &G);
	
	for (i = 1; i <= N; i++) 
		fscanf(stdin, "%d %d", &W[i], &P[i]);
}

void print_dp_matrix(int N, int G)
{
	int i, j;
	for (i = 0; i <= N; i++) {
		for (j = 0; j <= G; j++) 
			fprintf(stderr, "%2d ", V[i][j]);
		 fprintf(stderr, "\n");
	}
}

int main(void)
{
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	
	read_data();
	dp(N, G);
//	print_dp_matrix(N, G);

	fprintf(stdout, "%d\n", V[N][G]);
	
	return 0;
}