#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstdio>

#define MAXN 5001
#define MAXG 10001

using namespace std;

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

int N, G, Pmax;
int W[MAXN];
int P[MAXN];

int Optim[MAXG];

int main() {

	fin >> N >> G;

	for (int i = 1; i <= N; ++i) {
		fin >> W[i] >> P[i];
	}

	Optim[0] = 0;
	int sol = 0;

	for (int i = 1; i <= N; ++i)
		for (int j = G - W[i]; j >= 0; --j) {
			if (Optim[j + W[i]] < Optim[j] + P[i]) {
				Optim[j + W[i]] = Optim[j] + P[i];

				if (Optim[j + W[i]] > sol)
					sol = Optim[j + W[i]];
			}
		}

	fout << sol;

	return 0;
}