#include <fstream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

class InParser
{
private:
	FILE* fin;
	char* buff;
	int sp;
	char readch()
	{
		++sp;
		if (sp == 4096)
		{
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
public:
	InParser(const char* nume)
	{
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	InParser& operator >> (int& n)
	{
		char c;
		while (!isdigit(c = readch()));
		n = c - '0';
		while (isdigit(c = readch()))
			n = n * 10 + c - '0';
		return *this;
	}
};

InParser fin("rucsac.in");
ofstream fout("rucsac.out");

const int NMAX = 5001;
const int GMAX = 10001;

int optim[GMAX];
pair <int, int> p[NMAX];
int n, g, sol;

int main()
{
	fin >> n >> g;
	for (int i = 1; i <= n; ++i)
		fin >> p[i].first >> p[i].second;


	for (int i = 1; i <= n; ++i)
		for (int j = g - p[i].first; j >= 0; --j)
		{
			optim[j + p[i].first] = max(optim[j + p[i].first], optim[j] + p[i].second);
			sol = max(sol, optim[j + p[i].first]);
		}

	fout << sol << " ";
	return 0;
}