#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int max(int, int);

int n, g;
int w[5005], p[5005], dp[2][10005];

int main()
{
	fin >> n >> g;
	for (int i = 1; i <= n; i++)
		fin >> w[i] >> p[i];

	int l = 0;
	for (int i = 1; i <= n; i++, l = 1 - l)
	{
		for (int j = 1; j <= g; j++)
		{
			dp[l][j] = dp[1 - l][j];

			if (w[i] <= j)
				dp[l][j] = max(dp[l][j], dp[1 - l][j - w[i]] + p[i]);
		}
	}

	fout << dp[1 - l][g];
	return 0;
}

int max(int a, int b)
{
	return a > b ? a : b;
}