#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

int main() {
	ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

	int n, g;
	fin >> n >> g;

	vector<int> costs(n);
	vector<int> values(n);

	for (int i = 0; i < n; i++) {
		fin >> costs[i] >> values[i];
	}

	vector<int> dp(g + 1, 0);

	for (int i = 0; i < n; i++) {
		int current_cost = costs[i];
		int current_value = values[i];

		for (int cw = g; cw >= current_cost; cw--) {
			dp[cw] = max(dp[cw], dp[cw - current_cost] + current_value);
		}
	}

	fout << dp[g] << endl;

	fin.close();
	fout.close();

	return 0;
}