#include <vector>
#include <fstream>

//varianta pseudo polinomiala.

int n = 0, w = 0;
unsigned char DP[10000][5000] = {};
std::vector<int>
val,
weight;

//
int f(int greutate, int obiect)
{
	if (greutate <= 0 || obiect < 0)
	{
		return 0;
	}

	if (DP[greutate][obiect] != 0xff)
	{
		return DP[greutate][obiect];
	}

	//daca nu incape obiectul nu il folosim
	if (greutate < weight[obiect])
	{
		//nu mai e nevoie de memorare deoarece se face in recursie
		return f(greutate, obiect - 1);
	}

	//incercam cu obiect si fara obiect
	auto r = std::max(f(greutate - weight[obiect], obiect - 1) + val[obiect], f(greutate, obiect - 1));
	DP[greutate][obiect] = r;
	return r;
}

int main()
{

	std::ifstream in("rucsac.in");
	in >> n >> w;

	val.reserve(n);
	weight.reserve(n);

	for (int i = 0; i < n; i++)
	{
		int greutate, valoare;
		in >> greutate >> valoare;
		weight.push_back(greutate);
		val.push_back(valoare);
	}


	//initializam matricea
	for (int i = 0; i <= w; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i == 0 || j == 0)
			{
				DP[i][j] = 0;
			}
			else
			{
				DP[i][j] = 0xff;
			}
		}
	}

	std::ofstream of("rucsac.out");
	of << f(w, n - 1);

	return 0;
}