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