#include <fstream>
#include <algorithm>

using namespace std;

ifstream fi("rucsac.in");
ofstream fo("rucsac.out");

const int maxn = 3000;

struct obj {
	int profit, greutate;
} numere[maxn * 100 + 1];

int pmax;

int sume[maxn + 1];
void rucsac();

bool cmp(obj a, obj b)
{
	return a.greutate<b.greutate;
}

int N, G;

int main()
{
	fi >> N >> G;
	for (int i = 1;i <= N;i++)
		fi >> numere[i].greutate >> numere[i].profit;
	//sort(numere+1, numere+N+1, cmp);
	rucsac();
	fo << pmax - 1;
	return 0;
}

void rucsac()
{

	sume[0] = 1;
	int start = 0;
	for (int j = 1;j <= N;j++)
	{
		for (int i = start;i >= 0;i--)
		{
			if (sume[i] != 0)
			{
				if (sume[i + numere[j].greutate]<sume[i] + numere[j].profit)
					sume[i + numere[j].greutate] = sume[i] + numere[j].profit;
				if (i + numere[j].greutate>start)
					start = i + numere[j].greutate;
				if (sume[i] + numere[j].profit>pmax && i<G)
					pmax = sume[i] + numere[j].profit;
			}
		}
		if (start>G)
			return;
	}

	return;
}