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

#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#endif

int dp[10001];

int main() {
	int n, g, w, p, rasp=0;
	fin >> n >> g;
	for (int i=0; i<n; i++) {
		fin >> w >> p;
		for (int gcur=g; gcur>=w; gcur--) {
			dp[gcur] = max(dp[gcur], dp[gcur - w] + p);
		}
	}
	for (int gcur=0; gcur<=g; gcur++)
		rasp = max(rasp, dp[gcur]);
	fout << rasp;
}