#include <fstream>
#include <cstring>

using namespace std;

struct rucsac {
	int g, v;
} o;
long int g[10005], n, G, m;

int main ()
{
	ifstream fin ("rucsac.in");
	fin >> n >> G;
	memset (g, -1, sizeof(g));
	g[0] = 0;
	for (int i = 0; i < n; ++i)
	{
		fin >> o.g >> o.v;
		for (int j = G - o.g; j >= 0; --j)
			if (g[j] != -1 && g[j+o.g] < g[j] + o.v)
			{
				g[j+o.g] = g[j] + o.v;
				if (g[j+o.g] > m)
					m = g[j+o.g];
			}
	}
	fin.close ();
	ofstream fout ("rucsac.out");
	fout << m;
	fout.close ();
	return 0;
}