#include<fstream>
#define DIM1 5001
#define DIM2 10001
using namespace std; 

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

int Profit[DIM1][DIM2];
int N, G, Sol;
int W[DIM1], P[DIM1];

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 = 1; j <= G; j++)
			{
				Profit[i][j] = Profit[i-1][j];  //nu punem prima data obiectul curent
				if( W[i] <= j )
					Profit[i][j] = max(Profit[i][j], Profit[i-1][j-W[i]] + P[i] );  // numai in cazul in care maximizez profitul
		}
			Sol = Profit[N][G];
			out << Sol; 
			
	return 0;
}