#include <iostream>
#include <fstream>
#include <vector>
#define MAX 5005
#define LL long long
using namespace std;

int pos[MAX];
LL prof[MAX];

int main() {
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	LL n, g, x, maxv = 0;
	vector <LL> w, p;
	fin >> n >> g;
	for (int i = 0; i < n; ++i) {
		fin >> x;
		w.push_back(x);
		fin >> x;
		p.push_back(x);
	}
	pos[0] = 1;
	prof[0] = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = g; j >= 0; --j) {
			if(j + w[i] <= g && pos[j]) {
				pos[j + w[j]] = 1;
				prof[j + w[j]] = max(prof[j+w[i]], prof[j] + p[i]);
				maxv = max(prof[j + w[j]], maxv);
			}
		}
	}
	fout << maxv;
	return 0;
}