#include <stdio.h>
#include <algorithm>
using namespace std;
int i,j,n,gmax,w[5001], p[5001], matrice[2][10001],cur,ok;
int main () {
	FILE *f,*g;
	f=fopen("rucsac.in", "r");
	g=fopen("rucsac.out", "w");
	fscanf(f, "%d %d", &n,&gmax);
	for (i=1; i<=n; i++) fscanf(f, "%d %d", &w[i],&p[i]);
	for (i=1; i<=n; i++)
		for (j=0; j<=gmax; j++)
		{	
			if (i%2)
			{
				matrice[1][j]=matrice[0][j];
				if (w[i]<=j) matrice[1][j]=max(matrice[1][j], matrice[0][j-w[i]]+p[i]);
				//fprintf(g, "(%d %d): %d ? %d; %d\n", i,j,matrice[0][j],matrice[0][j-w[i]]+p[i],j-w[i]);
			}
			else
			{
				matrice[0][j]=matrice[1][j];
				if (w[i]<=j) matrice[0][j]=max(matrice[0][j], matrice[1][j-w[i]]+p[i]);
				//fprintf(g, "(%d %d): %d ? %d; %d\n", i,j,matrice[0][j],matrice[0][j-w[i]]+p[i],j-w[i]);
			}
		}
	/*for (i=0; i<=1; i++, fprintf(g, "\n"))
		for (j=0; j<=gmax; j++)
			fprintf(g, "%d ", matrice[i][j]);*/
	//for (i=1; i<=n; i++) fprintf(g, "%d %d\n", w[i],p[i]);
	if (!i%2) fprintf(g, "%d\n", matrice[1][gmax]);
	else fprintf(g, "%d\n", matrice[0][gmax]);
	fclose(f); fclose(g);
	return 0;
}