#include<stdio.h>
#include<limits.h>

#include<cstring>
using namespace std;

#define MAXN 5000
#define MAXG 10000

int N,G;

int* C0,* C1;

int* W, *P;

void rucsac(){
	if(W[0]>=1){
		if(W[0]<=G){
			for(int i=0;i<W[0];i++)
				C0[i]=0;
			for(int i=W[0];i<=G;i++)
				C0[i]=P[0];
		}
		else{
			for(int i=0;i<=G;i++)
				C0[i]=0;
			//memset(C0,0,(G+1)*sizeof(int));
		}
	}
	else{
		for(int i=0;i<=G;i++)
			C0[i]=P[0];
		//memset(C0,P[0],(G+1)*sizeof(int));
	}
	int cost,*A;
	for(int i=1;i<N;i++){
		for(int j=0;j<=G;j++){
			cost=C0[j];
			if(W[i]<=j){				
				if(cost<(C0[j-W[i]]+P[i]))
					cost=C0[j-W[i]]+P[i];
			}
			C1[j]=cost;
		}
		A=C0;
		C0=C1;
		C1=A;	
	}
}

int main(){
	
	freopen("rucsac.in","rt",stdin);
	//freopen("test11.in","rt",stdin);
	freopen("rucsac.out","wt",stdout);
	
	scanf("%d %d",&N,&G);
	
	W=new int[N];
	P=new int[N];

	C0=new int[G+1];
	C1=new int[G+1];

	for(int i=0;i<N;i++){
		scanf("%d %d",&W[i],&P[i]);
	}

	rucsac();
	printf("%d\n",C0[G]); 

	return 0;
}