// 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;

// Vom rezolva problema rucsacului in varianta discreta (0/1) folosind programare dinamica, alegand optim la fiecare pas.

// Definirea starii (a subproblemei):
// `dp[i][g]` - reprezinta profitul maxim care se poate obtine daca iau in considerare doar primele `i` obiecte, fara a depasi capacitatea `g` a rucsacului.

// Parcurgem toate posibilitatile de perechi (i, g), cu i <= n si g <= gMax si definim relatia de recurenta:
// - daca obiectul i incape in rucsac (g >= greutate[i]), verificam cum putem maximiza profitul: 
//     - fie adaugand obiectul in rucsac, pe langa celelalte adaugate deja (dp[i][g] = dp[i - 1][g - greutate[i]] + valoare[i])
//     - fie ignorandu-l (dp[i][g] = dp[i-1][g])
// Observam ca la fiecare iteratie, avem nevoie doar de linia anterioara din dp.
// Asadar, putem optimiza algoritmul transformand matricea dp in vector.
// Astfel, recurenta devine: dp[g] = MAX(dp[g - greutate[i]] + valoare[i], dp[g]), daca g >= greutate[i].
// Pentru ca ne folosim de greutati anterioare (dp[g - greutate[i]]), vom parcurge valorile lui g descrescator.

// Cazul de baza:
// dp[0][g] = 0 pentru orice g (nu alegem niciun obiect)
// dp[i][0] = 0 pentru orice i (capacitate 0)
// Folosind vector pentru dp, cazul de baza se rezuma la: dp[g] = 0, pentru oricare g.
// Tabloul dp este initializat implicit cu 0, prin declararea lui globala.

// Solutia se gaseste in matrice la pozitia dp[n][gMax], respectiv in vector la pozitia dp[gMax].

// Complexitate: O(n * g)

int dp[10001];

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

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

	for(int i = 1; i <= n; i++) {
		for(int g = gMax; g >= greutate[i]; g--) {
			if(dp[g - greutate[i]] + valoare[i] > dp[g]) {
				dp[g] = dp[g - greutate[i]] + valoare[i];
			}
		}
	}

	fout << dp[gMax] << "\n";

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

	return 0;
}