#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <cctype>
using namespace std;

#ifdef INFOARENA
#define ProblemName "rucsac"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

template <class T> void readNum(T &nr) {
	nr = 0;
	T sign = 1;
	char c;
	while (!isdigit(c = getchar()))
		(c == '-') && (sign = -1);
	do {
		nr = nr * 10 + c - '0';
	} while (isdigit(c = getchar()));
	nr *= sign;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	int N, G;
	readNum(N); readNum(G);
	vector<int> W(N), P(N);
	for (int i = 0; i < N; i++) {
		readNum(W[i]); readNum(P[i]);
	}
	vector<int> *v1 = new vector<int>(G + 1, 0);
	vector<int> *v2 = new vector<int>(G + 1);
	(*v2)[0] = 0;
	int sol = 0;
	for (int j = 0; j < N; j++) {
		for (int i = 0; i <= G; i++) {
			if (i >= W[j]) {
				(*v2)[i] = max((*v1)[i], (*v1)[i - W[j]] + P[j]);
				if ((*v2)[i] > sol)
					sol = (*v2)[i];
			}
			else
				(*v2)[i] = (*v1)[i];
		}
		swap(v1, v2);
	}
	printf("%d\n", sol);
	return 0;
}