// https://www.infoarena.ro/problema/rucsac

#include<fstream>

using namespace std;

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

int greutate[5001], valoare[5001];
int n, gMax;

// matricea pd[i][j] memoreaza valoarea maxima a rucsacului de capacitate j kg, luand in considerare primele i obiecte din lista
// fiind declarata global, matricea e initializata cu 0
// astfel pd[0][j] (nu punem niciun obiect in rucsac) si pd[i][0] (rucsac de 0 kg) sunt 0, nefiind nevoie de o initializare manuala coloane 0 si liniei 0
int pd[5001][5001];

int max(int x, int y) {
	if(x >= y) {
		return x;
	}

	return y;
}

int main() {
	fin >> n >> gMax;

	for(int i = 1; i <= n; i++) {
		fin >> greutate[i] >> valoare[i];
	}

	for(int ob = 1; ob <= n; ob++) {
		for(int g = 1; g <= gMax; g++) {
			if(g - greutate[ob] < 0) {
				// obiectul ob nu are cum sa incapa intr-un rucsac gol cu capacitatea g, deci il lasam in afara rucsacului
				pd[ob][g] = pd[ob - 1][g];
			} else {
				// obiectul ob poate incaprea in rucsacul cu capacitatea g

				// calculez valoarea rucsacului daca nu adaug obiectul in el
				int valNuAdaug = pd[ob - 1][g]; // nu il adaug, deci adaug doar obiecte pana la obiectul ob - 1 inclusiv

				// calculez valoarea rucsacului daca adaug obiectul ob in el
				// g - greutate[ob] -> ii fac loc in rucsac
				// valoarea reprezinta suma dintre valoarea primelor ob-1 obiecte (adica toate pana la el, dar pentru greutatea g-greutate[ob], pentru a avea loc in rucsac si obiectul ob) si valoarea obiectului ob
				int valAdaug = pd[ob - 1][g - greutate[ob]] + valoare[ob];

				// decid daca voi adauga sau nu obiectul in rucsac in functie de valoarea maxima pe care o pot obtine
				pd[ob][g] = max(valNuAdaug, valAdaug);
			}
		}
	}

	// valoarea maxima a rucsacului este pe ultima linia si coloana a matricei,
	// adica valoarea obtinuta pentru rucsacul de capacitate maxima, gMax, luand in considerare toate cele n obiecte
	fout << pd[n][gMax] << endl;


	fin.close();
	fout.close();

	return 0;
}