#include<fstream>
#define lim 5002
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,i,g,Profit[lim][2*lim];
struct dt {
	int w,p;
}
v[lim];
void read(){
	fin>>n>>G;
	for(int i=1;i<=n;i++)
		fin>>v[i].w>>v[i].p;
}
int max(int a,int b){
	if(a>b)
		return a;
	return b;
}
void solve(){
	for(int i=1;i<=n;i++){
		for(int g=0;g<=G;g++){
			if(v[i].w<=g){
				Profit[i][g]=max(Profit[i-1][g],Profit[i-1][g-v[i].w]+v[i].p);
			}
			else
				Profit[i][g]=Profit[i-1][g];
		}
	}
}
void print(){
	fout<<Profit[n][G];
}
int main (){
	read();
	solve();
	print();
	return 0;
}