#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[3][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]);
	for(int i=1;i<=n;i++){
		nr++;
		if(nr==3)
			nr=1;
		for(int j=1;j<=gg;j++){
			if(nr==2){
			if(j-G[i]>=0)
				x[2][j]=max(max(x[1][j],x[2][j-1]),x[1][j-G[i]] + P[i]);
			else
				x[2][j]=x[1][j];
			}
			else{
				if(j-G[i]>=0)
				x[1][j]=max(max(x[2][j],x[1][j-1]),x[2][j-G[i]] + P[i]);
			else
				x[1][j]=x[2][j];
			}
		}
		
	}
	if(n%2==0)
		fprintf(g,"%d",x[1][gg]);
	else
		fprintf(g,"%d",x[2][gg]);
	return 0;
}