#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[MAX_N][MAX_N];

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

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

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