#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstdio>

#define weight first
#define price second

using namespace std;

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

int N, G;
pair<int, int> v[5005];
int matrix[5005][10005];

int Solve(int nrObject, int WeightLeft) {
	if (matrix[nrObject][WeightLeft])
		return matrix[nrObject][WeightLeft];

	int result;

	if (nrObject == 0 || WeightLeft == 0)
		result = 0;

	else if (v[nrObject].weight > WeightLeft)
		result = Solve(nrObject - 1, WeightLeft);

	else {
		int t1 = Solve(nrObject - 1, WeightLeft);
		int t2 = Solve(nrObject - 1, WeightLeft - v[nrObject].weight) + v[nrObject].price;

		result = max(t1, t2);
	}

	matrix[nrObject][WeightLeft] = result;

	return result;
}

int main() {

	fin >> N >> G;

	for (int i = 1; i <= N; ++i) {
		fin >> v[i].weight >> v[i].price;
	}

	fout << Solve(N, G);

	return 0;
}