#include<fstream>
#include<algorithm>
using namespace std;
#define NMax 5005
#define GMax 10005

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int N,G,W[NMax],V[NMax];
int Sol[2][GMax];

void citire(){
	fin>>N>>G;
	for(int i=1;i<=N;i++){
		fin>>W[i]>>V[i];
	}
}

// Sol[i][j]= max( Sol[i-1][j], Sol[i-1][j-W[i]]+C[i]);
void solve(){
	int i,j,q;
	for(i=1;i<=N;i++){
		for(j=0;j<=G;j++){
			if(j>=W[i])
				Sol[1][j] = max(Sol[0][j], Sol[0][j-W[i]]+V[i]);
			else
				Sol[1][j] = Sol[0][j];
		}
		for(q=0;q<=G;q++){
			Sol[0][q]=Sol[1][q];
		}
	}
}

int main(){
	
	citire();
	solve();
	fout<<Sol[1][G];
	
	fin.close();
	fout.close();
	return 0;
}