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

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

	int current = 1;
	int last = 0;

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

	std::cout << dp[last][G] << '\n';

	return 0;
}