#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 5005
#define GMAX 10005

int W[NMAX], P[NMAX];

int dp[NMAX][GMAX];
int N, G;

void compute()
{
	for(int i = 1; i <= N; ++i)
		for(int j = 0; j <= G; ++j){
			dp[i][j] = dp[i-1][j];
			
			if(j - W[i] >= 0)
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + P[i]);
		}	
}

int main()
{
	ifstream  in("rucsac.in");
	ofstream out("rucsac.out");
	
	in >> N >> G;
	for(int i = 1; i <= N; ++i)
		in >> W[i] >> P[i];
	
	compute();
	out << dp[N][G];
	
	return 0;
}