#include <fstream>

#define MAX_N ((const int)5000)
#define MAX_G ((const int)10000)

class Object
{
public:
	int weight;
	int profit;
};

int N, G;
Object object[MAX_N];
int prof[MAX_G];
int sol;

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

	fin>>N>>G;

	for (int i = 0; i < N; ++ i)
		fin>>object[i].weight>>object[i].profit;

	for (int i = 0; i < N; ++ i)
	{
		for (int j = G - object[i].weight; j >= 0; -- j)
		{
			if (prof[j + object[i].weight] < prof[j] + object[i].profit)
			{
				prof[j + object[i].weight] = prof[j] + object[i].profit;
				if (sol < prof[j + object[i].weight])
					sol = prof[j + object[i].weight];
			}
		}
	}

	fout<<sol;

	fin.close();
	fout.close();

	return 0;
}