#include <fstream>
#define MAX_OBJECTS 5001
#define MAX_WEIGHT 10001
#define MAX(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

int M[2][MAX_WEIGHT];
int P[MAX_OBJECTS], W[MAX_OBJECTS];

int main()
{
	ifstream ifs("rucsac.in");
	ofstream ofs("rucsac.out");
	
	int n, g; ifs >> n >> g;
	for (int i = 1; i <= n; ++i)
		ifs >> W[i] >> P[i];
	
	
	int p_row = 0; // Previous row
	int c_row = 1; // Current row
	for (int i = 1; i <= n; ++i)	
	{
		for (int w = 0; w <= g; ++w)
		{
			if (W[i] <= w)
				M[c_row][w] = MAX(M[p_row][w], M[p_row][w - W[i]] + P[i]);
			else
				M[c_row][w] = M[p_row][w];
		}

		int aux = p_row;
		p_row = c_row;
		c_row = aux;
	}
	
	ofs << M[p_row][g];
	return 0;
}