#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit.
 Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare G.
 */

/*  Relatia de recurenta:
 *
 * P(i, G) =  max { P(i-1, G-w[i]) + p[i] , P(i-1, G) }
 * */


#define NMAX 5002
#define GMAX 10002
int N, G;
int p[NMAX];
int w[NMAX];

int P[2][GMAX];

int smax = 0;
int im, jm;

void solutie_rucsac()
{
	int i, j;

	memset(P[0], 0, N*sizeof(int));
	P[0][0] = 0;
	P[1][0] = 0;

	for( i = 1; i <=N; i++ ) {
		for( j = 1; j <= G; j++ ) {
			if(j< w[i])
				P[i%2][j] = P[(i-1)%2][j];
			else
			if(P[(i-1)%2][j] >= P[(i-1)%2][j-w[i]]+ p[i])
				P[i%2][j] = P[(i-1)%2][j];
			else
				P[i%2][j] = P[(i-1)%2][j-w[i]]+ p[i];

			if(smax < P[i%2][j]) {
				smax = P[i%2][j];
				im = i; jm = j;
			}
		}
	}
}

int main()
{
	FILE *f, *fout;
	int i;

	f = fopen("rucsac.in", "r");

	fscanf(f, "%d %d", &N, &G);
	for(i  = 1 ; i <= N; i++ ) {
		fscanf(f, "%d %d", &w[i], &p[i]);
	}
	fclose(f);

	solutie_rucsac();

	fout = fopen("rucsac.out", "w");
	fprintf(fout, "%d\n", smax);
	fclose(fout);

	return 0;
}