#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[5001], P[5001];
int dp[2][10001];

int main() {
	ifstream cin("rucsac.in");
	ofstream cout("rucsac.out");
	cin >> N >> G;
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> P[i];
	}
	for (int i = 1; i <= N; i++) {
		for (int w = 0; w <= G; w++) {
			dp[i & 1][w] = dp[(i - 1) & 1][w];
			if (W[i] <= w) {
				dp[i & 1][w] = max(dp[i & 1][w], P[i] + dp[(i - 1) & 1][w - W[i]]);
			}
		}
	}
	cout << dp[N & 1][G] << endl;
	return 0;
}