#include<fstream>
#define Nmax 5001
#define Gmax 10001
using namespace std;

int Cmax[Gmax], uz[Gmax][Nmax], c[Nmax], g[Nmax];
int i, j, G, n, k;

int main()
{
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);
	
	scanf("%d%d%", &n, &G);
	for(i=1;i<=n;i++)
		scanf("%d%d", &g[i], &c[i]);
	for(i=1;i<=G;i++)
		Cmax[i]=-1;

	for(i=1;i<=G;i++)
		for(j=1;j<=n;j++)
			if(g[j]<=i && Cmax[i-g[j]]!=-1 && !uz[i-g[j]][j])
				if(Cmax[i]<c[j]+Cmax[i-g[j]])
				{
					Cmax[i]=c[j]+Cmax[i-g[j]];
					for(k=1;k<=n;k++)
						uz[i][k]=uz[i-g[j]][k];
					uz[i][j]=1;
				}
	printf("%d\n", Cmax[G]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}