#include <array>
#include <fstream>
#include <iterator>
#include <cmath>

struct Obiect
{
	int W, P;

	friend std::istream& operator>>(std::istream& in, Obiect& o)
	{
		in >> o.W >> o.P;
		return in;
	}
};

int main()
{
	std::ifstream FIn("rucsac.in");
	std::ofstream FOut("rucsac.out");

	std::array<Obiect, 10002U> Obiecte = { 0 };
	std::array<std::array<int, 10001U>, 2U> DP = { 0 };

	int N, G;
	int PrevIndex = 0, CurIndex = 1;

	FIn >> N >> G;
	std::copy((std::istream_iterator<Obiect>(FIn)), std::istream_iterator<Obiect>(), std::next(Obiecte.begin()));

	for (int i = 1; i <= N; i++)
	{
		for (int w = 0; w <= G; w++)
		{
			if (Obiecte[i].W <= w)
				DP[CurIndex][w] = std::max(DP[PrevIndex][w], Obiecte[i].P + DP[PrevIndex][w - Obiecte[i].W]);
			else
				DP[CurIndex][w] = DP[PrevIndex][w];
		}

		int Temp = CurIndex;
		CurIndex = PrevIndex;
		PrevIndex = Temp;
	}

	FOut << DP[PrevIndex][G];

	return 0;
}