#include <cstdio>
#include <algorithm>

using namespace std;

int N, G, result[5001][10001];

struct obj { int w; int p; } els[5001];

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

	scanf("%d %d\n", &N, &G);

	for (int i = 0; i < N; ++i) {
		scanf("%d %d\n", &els[i].w, &els[i].p);
	}

	for (int elIndex = 0; elIndex < N; ++elIndex) {
		obj el = els[elIndex];

		for (int currG = el.w; currG <= G; ++currG) {
			int val = result[currG - el.w][elIndex] + el.p;

			if (result[currG - el.w][elIndex] != 0 || currG == el.w) {
				result[currG][elIndex+1] = max(result[currG][elIndex], val);
			} else {
				result[currG][elIndex+1] = result[currG][elIndex];
			}
		}
	}

	// for (int i = 1; i <= G; ++i) {
	// 	for (int j = 1; j <= N; ++j) {
	// 		printf("%d ", result[i][j]);
	// 	}
	//
	// 	printf("\n");
	// }

	while (result[G][N] == 0) {
		--G;
	}

	printf("%d\n", result[G][N]);

	return 0;
}