#include<fstream>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
int n, g, dp[5005][10005], w[5005], p[5005];
int main()
{
	in>>n>>g;
	for (int i=1; i<=n; i++)
		in>>w[i]>>p[i];
	for (int i=1; i<=n; i++)
		for (int j=0; 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];
	out.close();
	return 0;
}