#include <iostream>
#include <fstream>
#define NMAX 5000
#define GMAX 10000

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

int N, G;
int dp[2][1 + GMAX];
int weigth[1 + NMAX];
int profit[1 + NMAX];

int main() {

	std::cin >> N >> G;

	for ( int i = 1; i <= N; ++i )
		//std::cin >> weigth[i] >> profit[i];
		fin >> weigth[i] >> profit[i];
	int current = 1;
	int last = 0;
	int ans = 0;

	for ( int i = 1; i <= N; ++i ) {
		for ( int w = 0; w <= G; ++w ) {
			if ( w >= weigth[i] ) 
				dp[current][w] = std::max ( dp[last][w], dp[last][w - weigth[i]] + profit[i] );
			else
				dp[current][w] = dp[last][w];
			ans = std::max( ans, dp[current][w] );
		}
		std::swap ( current, last );
	}

	//std::cout << dp[last][G] << '\n';
	fout << ans << '\n';
	
	return 0;
}