#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#define LL long long
#define DN 10005
using namespace std;

int pos1[DN], pos2[DN], w[DN], p[DN], maxp1[DN], maxp2[DN];

int main() {
	int n, g, a, b, maxx = 0;
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	cin >> n >> g;
	for(int i = 0; i < n; ++i) {
		cin >> w[i] >> p[i];
	}
	pos1[0] = 1;
	for(int j = 0; j < n; ++j) {
		for(int i = 1; i <= g; ++i) {
			if(pos1[i - w[j]]) {
				pos2[i] = 1;
				maxp2[i] = max(maxp2[i], p[j] + maxp1[i - w[j]]);
				maxx = max(maxx, maxp2[i]);
			}
		}
		for(int i = 1; i <= g; ++i){
			pos1[i] += pos2[i];
			maxp1[i] = max(maxp1[i], maxp2[i]);
		}
	}
	cout << maxx;
	return 0;
}