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

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N, G, optim[10001], p[10001], w[10001], sol;
int main(){
	f>>N>>G;
	for (int i = 1; i<=N; ++i)
		f>>w[i]>>p[i];
	for (int i = 1; i<= N; ++i){
		for (int j = G-w[i]; j >= 0; --j){
			if (optim[j+w[i]] < optim[j] + p[i])
				optim[j+w[i]] = optim[j] + p[i];
			if (optim[j+w[i]] > sol)
				sol = optim[j+w[i]];
		}
	}
	g<<sol;
}