#include <iostream>
#include <fstream>

using namespace std;

#define MAX(a,b) ((a) > (b) ? (a) : (b))

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


int G,N,Pmax = 0;
const int n = N,MAXN = 5000,MAXG = 10000;
int W[MAXG], P[MAXN];
int D[MAXG][MAXN];


void afisare() {
	out << endl;
	for (int i = 0; i <= N; i++) {
		out << endl;
		for (int j = 0; j <= G; j++) {
			out << D[i][j] <<"   ";
		}
	}
}
void citire() {
	in >> N >> G;
	for (int i = 1; i <= N; i++) {
		in >> W[i] >> P[i];
	}

}
void F() {
	citire();
	for (int i = 1; i <= N; ++i) {
		for (int g = 0; g <= G; ++g) {

			D[i][g] = D[i - 1][g];

			if (W[i] <= g) {
				D[i][g] = MAX(D[i][g], D[i - 1][g - W[i]] + P[i]);//relatia de recurenta
			}

		}

	}

	Pmax = D[N][G];
	out << Pmax;

}

int main()
{
	F();

	return 0;
}