#include <fstream>
#include <vector>
using namespace std;

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	int N, G, pmax = 0;
	in >> N >> G;
	vector<int> w(N, 0);
	vector<int> p(N, 0);
	vector<int> val(G + 1, 0);
	
	for (int i = 0; i < N; i++) {
		in >> w[i] >> p[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = G - w[i]; j >= 0; j--) {
			if (val[j + w[i]] < val[j] + p[i]) {
				val[j + w[i]] = val[j] + p[i];
				if (pmax < val[j + w[i]])
					pmax = val[j + w[i]];
			}
		}
	}

	out << pmax;
	in.close();
	out.close();
	return 0;
}