#include <fstream>
using namespace std;

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

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

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

int main()
{
	int n, g;
	read(n, g);
	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;
}