#include <iostream>
#include <fstream>

std::ifstream in("rucsac.in");
std::ofstream out("rucsac.out");

const int Nmax = 5001;
const int Gmax = 10001;

int main()
{
	int Weight[Nmax];
	int Profit[Nmax];
	int Optim[Gmax];

	int n;
	in >> n;
	int g;
	in >> g;

	for (int i = 1; i <= n; i++)
	{
		in >> Weight[i] >> Profit[i];
	}

	int Smax = 0;
	Optim[0] = 0;

	for (int i = 1; i <= n; i++)
	{
		for (int j = g - Weight[i]; j >= 0; j--)
		{
			if (Optim[j + Weight[i]] < Optim[j] + Profit[i])
			{
				Optim[j + Weight[i]] = Optim[j] + Profit[i];
				if (Optim[j + Weight[i]] > Smax)
					Smax = Optim[j + Weight[i]];
			}
		}
	}

	out << Smax;
}