#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[2][10005];

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

	fill(dp[0], dp[0] + 10005, 0);
	fill(dp[1], dp[1] + 10005, 0);

	int cur_line = 0;
	// incerc sa rezolv problema rucsacului folosind 1 dimensiune
	for (obiect = 1; obiect <= n; obiect++, cur_line = 1 - cur_line){

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

	fout << dp[g];

	return 0;
}