#include<cstdio>
#include<algorithm>
#define maxm 10005
#define maxn 5005
using namespace std;
FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");
int x[2][maxm],n,gg,y,G[maxn],P[maxn],nr=1;
int main (){
	fscanf(f,"%d%d",&n,&gg);
	for(int i=1;i<=n;i++)
		fscanf(f,"%d%d",&G[i],&P[i]);
	nr=0;
	for(int i=1;i<=n;i++,nr=1-nr){
		for(int j=1;j<=gg;j++){
			if(j-G[i]>=0)
				x[1-nr][j]=max(max(x[nr][j],x[1-nr][j-1]),x[nr][j-G[i]] + P[i]);
			else
				x[1-nr][j]=x[nr][j];
		}
	}
	if(n%2==0)
		fprintf(g,"%d",x[0][gg]);
	else
		fprintf(g,"%d",x[1][gg]);
	return 0;
}