#include <fstream>
#include <algorithm>
#define DMAX 5001
using namespace std;

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

int n, G;
int w[DMAX], p[DMAX];
int D[2][2 * DMAX];
bool uz[DMAX];

// Infoarena
int main(){
	int i, cw, l = 0;

	/* Vom tine un tablou bidimensional D, care va
	retine in celula de coordonate(i, cw)
	profitul maxim pe care-l putem obtine
	selectand o submultime a primelor i elemente,
	a caror greutate insumata este egala cu cw.
	Presupunem ca avem calculate solutiile pentru
	orice greutate mai mica sau egala ca G, selectand
	o submultime din primele i-1 elemente. Construim
	solutia pentru i elemente, folosindu - ne de
	urmatoarea recurenta : D[i][cw] = maximul
	dintre D[i - 1][cw], situatie in care nu
	adaugam elementul i la solutia precedenta,
	si D[i - 1][cw - W[i]] + P[i], cand adaugam
	la cea mai buna solutie cu greutatea cw - W[i]
	elementul i, obtinand greutatea W[i] si un profit
	mai mare cu P[i].
	Raspunsul final se va afla in starea D[N][G] */

	fin >> n >> G;
	for (i = 1; i <= n; i++) fin >> w[i] >> p[i];

	for (i = 1; i <= n; i++, l = 1 - l){
		for (cw = 0; cw <= G; cw++){
			// Mai intai nu punem obiectul i.
			D[1 - l][cw] = D[l][cw];

			// Daca acest lucru duce la o solutie curenta mai buna, 
			//adaugam obiectul i la o solutie anterioara.
			if (w[i] <= cw)
				D[1 - l][cw] = max(D[1 - l][cw], D[l][cw - w[i]] + p[i]);
		}
	}

	fout << D[l][G];

	return 0;
}


// my first main .. 0p
/*
int main(){
	int i, j, ok, poz;
	int sum = 0, weight = 0;
	int sumAct, weightAct;

	fin >> n >> G;
	for (i = 1; i <= n; i++) fin >> w[i] >> p[i];

	ok = 1;
	while (ok){
		ok = 0;
		poz = 0;
		sumAct = sum;
		weightAct = weight;
		for (i = 1; i <= n; i++){
			if (!uz[i] && weight + w[i] <= G && sum + p[i] > sumAct){
				poz = i;
				sumAct = sum + p[i];
				weightAct = weight + w[i];
				ok = 1;
			}
		}
		uz[poz] = true;
		sum = sumAct;
		weight = weightAct;
	}

	fout << sum;

	return 0;
	}*/