// 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];
// OPTIMIZARE: fiindca in algoritm ne trebuie doar linia anterioara din matrice, nu are rost sa pastram intreaga matrice si putem folosi un singur vector
int pd[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++) {
		// in mod normal am parcurge vectorul de la stanga la dreapta, dar, in algoritm, folosim: dp[g - greutate[i]]
		// daca parcurgem de la stanga a dreapta vectorul, dp[g - greutate[i]] ar putea fi deja actualizat
		// pentru a evita aceasta situatie, parcurgem vectorul de la dreapta la stanga.
		// 
		// OPTIMIZARE: parcurgem pana cand g ajunge la greutate[ob]
		// daca g este mai mic decat greutate[ob], se pastreaza valoarea obtinuta fara a lua obiectul ob in considerare, fiindca obiectul nu ar incapea in rucsac nici daca l-am pune singur
		for(int g = gMax; g >= greutate[ob]; g--) {
			// obiectul ob poate incaprea in rucsacul cu capacitatea g

			// calculez valoarea rucsacului daca nu adaug obiectul in el
			int valNuAdaug = pd[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[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[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[gMax] << endl;


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

	return 0;
}