#include <fstream>
using namespace std;

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

int n, g, w[5001], p[5001], dp[5001][10001];

void read()
{
	in >> n >> g;
	for(int i = 1; i <= n; ++i)
		in >> w[i] >> p[i];
}

int main()
{
	read();
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= g; ++j)
		{
			if(j < w[i]) dp[i][j] = dp[i-1][j];
			else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + p[i]);
		}
	out << dp[n][g];
	return 0;
}