#include <fstream>
#include <algorithm>

const int MAX_N = 5001;
const int MAX_G = 10001;

int n, g, best = 0;
int w[MAX_N] = { 0 };
int p[MAX_N] = { 0 };
int dp[MAX_G] = { 0 };

void read()
{
	std::ifstream input("rucsac.in");
	input >> n >> g;
	for (int idx(1); idx <= n; ++idx) {
		input >> w[idx] >> p[idx];
	}
	input.close();
}

void print()
{
	std::ofstream output("rucsac.out");
	output << best << '\n';
	output.close();
}

void dynamic()
{
	for (int idx(1); idx <= n; ++idx) {
		for (int weight(g - w[idx]); weight >= 0; --weight) {
			dp[weight + w[idx]] = std::max(dp[weight + w[idx]], dp[weight] + p[idx]);
		}
	}
	for (int weight(g); weight >= 0; --weight) {
		best = std::max(best, dp[weight]);
	}
}

int main()
{
	read();
	dynamic();
	print();
	return 0;
}