#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 5003

int N, G;
int W[NMAX], Cost[NMAX];
int Sol[3][2 * NMAX];

void Read_Data ()
{
	scanf ("%d %d", &N, &G);
	for (int i = 1; i <= N; ++i)
		scanf ("%d %d", &W[i], &Cost[i]);
}

void Solve ()
{
	int line = 0;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= G; ++j)
		{
			Sol[i % 2][j] = Sol[(i - 1) % 2][j];

			if (W[i] <= j)
				Sol[i % 2][j] = max (Sol[i % 2][j], Sol[(i - 1) % 2][j - W[i]] + Cost[i]);
		}
	}

	printf ("%d\n", Sol[N % 2][G]);
}

int main ()
{
	freopen ("rucsac.in", "r", stdin);
	freopen ("rucsac.out", "w", stdout);

	Read_Data ();

	Solve ();

	return 0;
}