//rucsac O(N) memorie cu memoizare
#include<fstream>
#define DIM1 5001
#define DIM2 10001
using namespace std; 

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

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