#include <fstream>
using namespace std;
 
ifstream in("rucsac.in");
ofstream out("rucsac.out");
 
int w[5001], p[5001], dp[2][10001];

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