#include <bits/stdc++.h>
// #include <fstream>

using namespace std;

int main(){

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

	int obiect, i, j, n, g, greutate[5005], valoare[5005], dp[10005], aux[10005];

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

	fill(dp, dp + 10005, 0);
	// incerc sa rezolv problema rucsacului folosind 1 dimensiune
	for (obiect = 1; obiect <= n; obiect++){
		copy(dp, dp + g, aux);

		for (j = 1; j <= g; j++){
			// daca nu incape in ghiozdan de unul singur
			if (j < greutate[obiect]){
				dp[j] = aux[j];
				continue;
			}
			// daca incape in ghiozdan decidem daca il bagam sau nu
			dp[j] = max(aux[j - greutate[obiect]] + valoare[obiect], aux[j]);
		}
	}

	fout << dp[g];

	return 0;
}