#include<fstream>
#include<algorithm>
using namespace std;
#define NMax 10000
#define GMax 5000

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

int N,G,W[NMax],V[NMax];
int Sol[NMax][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;
	for(i=1;i<=N;i++){
		for(j=0;j<=G;j++){
			if(j>=W[i])
				Sol[i][j] = max(Sol[i-1][j], Sol[i-1][j-W[i]]+V[i]);
			else
				Sol[i][j] = Sol[i-1][j];
		}
	}
}

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