#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct object {
	int weight, profit;
};
const int NMAX = 5055;
const int WMAX = 10505;

int N, G;
object A[NMAX];
int best[2][WMAX];

int main() {
	freopen("rucsac.in", "r", stdin);
	freopen("rucsac.out", "w", stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> G;
	for (int idx = 1; idx <= N; idx++) {
		cin >> A[idx].weight >> A[idx].profit;
	}

	best[0][0] = 0;
	for (int idx = 1; idx <= N; idx++) {
		// can always use prev result for a particular weight by not taking the current object
		memcpy(best[idx & 1], best[(idx - 1) & 1], sizeof(best[idx & 1]));
		for (int totalWeight = 0; totalWeight < WMAX; totalWeight++) {
			if (A[idx].weight > totalWeight) {
				best[idx & 1][totalWeight] = best[(idx - 1) & 1][totalWeight];
			} else {
				best[idx & 1][totalWeight] = max(
					best[(idx - 1) & 1][totalWeight],
					best[(idx - 1) & 1][totalWeight - A[idx].weight] + A[idx].profit);
			}
		}
	}

	int result = 0;
	for (int totalWeight = 0; totalWeight <= G; totalWeight++) {
		result = max(result, best[N & 1][totalWeight]);
	}
	printf("%d\n", result);
	return 0;
}