#include <fstream>

using namespace std;

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

struct obj {
	int greutate, profit;
};

obj numere[5001];
int sume[20001];

int N, G, sol;

void rucsac();

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

void rucsac()
{
	sume[0] = 1;
	int start = 0;
	for (int i = 1;i <= N;i++)
	{
		for (int j = start;j >= 0;j--)
		{
			if (sume[j] != 0)
			{
				int x = j + numere[i].greutate;
				int cost = sume[j] + numere[i].profit;
				if (cost > sume[x])
					sume[x] = cost;
				if (x > start)
					start = x;
				if (x<=G)
					if (cost > sol)
						sol = cost;
			}
		}
		
		if (start >= G)
			start = G;
	}
}