#include <iostream> 
#include <fstream>
#define NMAX 5001
#define GMAX 10001

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

int w[NMAX], v[NMAX], opt[GMAX];
int N, G;
int maxim, maxtake;
int main () {

	fin>>N>>G;
	
	for (int i = 1; i<=N; i++)
		fin>>w[i]>>v[i];

	for (int i=1; i<=N; i++) {
		for (int g=G; g>=0; g--) {
			maxim = opt[g];		
			if( g-w[i] < 0 )
				opt[g] = maxim;
			else{
			maxtake = v[i] + opt[g - w[i]]; 
			if( maxim <  maxtake )
				maxim = maxtake;
			opt[g] = maxim;
			}
		}			
	}	
	fout<<opt[G];
	
	return 0;
}