#include <fstream.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main ()
{
	int N, G, W[5010], P[5010], i, j;
	int m[2][10010];

	ifstream fin ("rucsac.in");
	fin >> N >> G;
	for (i = 1; i <= N; i++)
	{
		fin >> W[i] >> P[i];
	}
	fin.close ();

	memset (m, 0, sizeof (m));

	for (j = 1; j <= N; j++)
	{
		for (i = 1; i <= G; i++)
		{
			if (W[j] <= i) m[j % 2][i] = max (m[(j - 1) % 2][i], m[(j - 1) % 2][i - W[j]] + P[j]);
			else m[j % 2][i] = m[(j - 1) % 2][i];
		}
	}

	ofstream fout ("rucsac.out");
	fout << m[N % 2][G];
	fout.close ();
	return 0;
}