#include <fstream>

const int N_MAX = 5010;

using namespace std;

ifstream fin;
ofstream fout;

int cost[N_MAX], castig[N_MAX];
int best[2*N_MAX];

int main () {
	int N, G;
	
	fin.open("rucsac.in");
	fin >> N >> G;
	for (int i = 1; i <= N; i ++) {
		fin >> cost[i] >> castig[i];
	}
	fin.close();
	
	for (int i = 1; i <= N; i ++) {
		for (int j = G - cost[i]; j >= 0; j --) {
			if (best[j+cost[i]] < best[j] + castig[i]) {
				best[j+cost[i]] = best[j] + castig[i];
			}
		}
	}
	
	fout.open("rucsac.out");			
	fout << best[G];
	fout.close();
	
	return 0;
}