#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];
int n, g, sol, w, p;

int main()
{
	fin >> n >> g;
	for (int i = 1; i <= n; ++i)
	{
		fin >> w >> p;
		for (int j = g - w; j >= 0; --j)
		{
			if (optim[j] + p > optim[j + w])
				optim[j + w] = optim[j] + p;
			if (optim[j + w] > sol)
				sol = optim[j + w];
		}
	}

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