#include <fstream>
#define MAX_N 5005
#define MAX_G 10010

using namespace std;

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

int profit[MAX_N], cost[MAX_N], gr, n;
int dp[2][MAX_G];

void read ()
{
	f >> n >> gr;
	for (int i = 1; i <= n; i++)
		f >> cost[i] >> profit[i];
}

void solve ()
{
	int l = 0;
	for (int i = 1; i <= n; i++, l = 1 - l)
		for (int j = 0; j <= gr; j++)
		{
			dp[1 - l][j] = dp[l][j];
			if (cost[i] <= j)
				dp[1 - l][j] = max (dp[1 - l][j], dp[l][j - cost[i]] + profit[i]);
		}
	
	g << dp[l][gr];
	f.close();
	g.close();
}

int main ()
{
	read ();
	solve ();
	
	return 0;
}