#include <iostream>
#include <fstream>

using namespace std;

#define NMAX 5005
#define GMAX 10005

int W[NMAX], P[NMAX];

int dp[2][GMAX];
int N, G, k;

void compute()
{
	for(int i = 1; i <= N; ++i, k = 1 - k)
		for(int j = 0; j <= G; ++j){
			dp[1-k][j] = dp[k][j];
			
			if(j - W[i] >= 0)
				dp[1-k][j] = max(dp[k][j], dp[k][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[k][G];
	
	return 0;
}