#include <bits/stdc++.h>
using namespace std;

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

int W[5010], P[5010];
int best[10010];

int main() {

	int N, G;
	in >> N >> G;

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

	for(int i = 1; i <= N; ++i) {
		for(int j = G; j >= W[i]; --j) {
			best[j] = max(best[j], best[j - W[i]] + P[i]);
		}
	}
	
	out << best[G] << '\n';

	in.close(); out.close();

	return 0;
}