//============================================================================
// Name        : RucsacDiscret.cpp
// Author      : Teodor Cotet
// Version     :
// Copyright   : Your copyright notice
// Description : Rucsac in O(N*G) time O(G) memory , Ansi-style
//============================================================================

#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 5000;
const int GMAX = 10000;
const int BOUND = NMAX * GMAX;


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

int n; int g;
int w[NMAX + 1];
int p[NMAX + 1];
int best[BOUND + 1];
/* best[i] = max profit at weight i, using just current elements */

int main() {

	fin >> n >> g;

	for(int i = 1; i <= n; ++i)
		fin >> w[i] >> p[i];

	for(int i = 1; i <= n; ++i) {

		for(int j = g; j >= 0; --j)
			if(j >= w[i])
				best[j] = max(best[j], best[j - w[i]] + p[i]);
	}

	int sol = 0;

	for(int  i = g; i >= 0; --i)
		if(sol < best[i])
			sol = best[i];

	fout << sol << '\n';


	return 0;
}