#include <iostream>
#include <vector>
#include <fstream>

#define Inf 123456789

#define NMax 5005
#define GMax 10005

using namespace std;

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

int N, G;

std::vector<int> previousCost(GMax, 0);
std::vector<int> currentCost(GMax, 0);
std::vector<int> cost(NMax, 0);
std::vector<int> weight(NMax, 0);



int main() {
	
	fin >> N >> G;
	
	for (int i = 1; i <= N; ++i) {
		fin >> weight[i] >> cost[i]; 
	}

	for (int i = 1; i <= N; ++i) {
		for (int g = 0; g <= G; ++g) {
			currentCost[g] = previousCost[g];
			
			if (g - weight[i] >= 0)
				currentCost[g] = std::max(currentCost[g], cost[i] + previousCost[g - weight[i]]);
		}
		std::swap(previousCost, currentCost);
	}

	fout << previousCost[G] << '\n';

	return 0;
}