#include <iostream>
#include <fstream>

using namespace std;

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

int W[5010], P[5010];
int Best[10010];

int main ()
{
	int N, G, i, j;
	
	in >> N >> G;
	
	for (i = 1; i <= N; i ++)
		in >> W[i] >> P[i];
	
	for (i = 1; i <= N; i ++)
		for (j = G - W[i]; j >= 0; j --)
			if (Best[ j + W[i] ] < Best[j] + P[i])
				Best[ j + W[i] ] = Best[j] + P[i];
				
	out << Best[G];
	
	return 0;
}