#include <fstream>

using namespace std;

const bool MAXN = 10001;

int sum[MAXN];

int	main()
{
	int N;
	int G;
	int maxi;
	int w;
	int p;

	ifstream mama("rucsac.in");
	ofstream tata("rucsac.out");
	mama >> N;
	mama >> G;
	sum[0] = 0;
	maxi = 0;
	for (int j, i = 0; i < N; i += 1) {
		mama >> w;
		mama >> p;
		j = maxi;
		while (j >= 0) {
			if (sum[j + w] < sum[j] + p)
				sum[j + w] = sum[j] + p;
			j--;
		}
		maxi = maxi + w;
	}
	tata << sum[G];
	return 0;
}