#include <iostream>
#include <fstream>

#define GMAX 10000
#define NMAX 5000
#define max(a,b) a>b?a:b
using namespace std;

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

int N, G, l;
int w[NMAX+1], p[NMAX+1], W[GMAX+1];

int main() {
	fin >> N >> G;
	for (int i = 1; i <= N; i++)
		fin >> w[i] >> p[i];
	for (int i = 1; i <= N; i++, l = inc(l))
		for (int wcrt = G; wcrt >= w[i]; wcrt--) {
			W[wcrt] = max(W[wcrt], W[wcrt - w[i]] + p[i]);
		}
	fout << W[G] << endl;
}