#include <fstream>

using namespace std;

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

int N,G;
int D[5001],w[5001],p[5001];

void solve() {
	D[0]=0;
	for (int i=1;i<=N;i++) {
		for (int g=G;g>=w[i];g--) {
			if (D[g]<D[g-w[i]]+p[i]) {
				D[g]=D[g-w[i]]+p[i];
			}
		}
	}
}

int main() {
	in>>N>>G;

	for (int i=1;i<=N;i++) {
		in>>w[i]>>p[i];
	}

	solve();
	out<<D[G];

	return 0;
}