#include <fstream>
#include <vector>
#include <algorithm>

struct file_manip {

	std::ifstream fin;
	std::ofstream fout;

	file_manip(const char* filename) {
		std::string infilename  = std::string(filename) + ".in";
		std::string outfilename = std::string(filename) + ".out";
		fin.open(infilename.c_str());
		fout.open(outfilename.c_str());
	}

	template <class T>
	file_manip& operator << (const T& rhs) {
		fout << rhs;
		return *this;
	}
	template <class T>
	file_manip& operator >> (T& rhs) {
		fin >> rhs;
		return *this;
	}
};

int main()
{
	file_manip fm("rucsac");
	int N, G;
	fm >> N >> G;
	std::vector<int> best(G + 1, 0), prev(G + 1, 0);
	std::vector<std::pair<int, int>> v;
	v.reserve(N);
	std::generate_n(std::back_inserter(v), N, [&fm]() -> std::pair<int, int> { int w, p; fm >> w >> p; return std::make_pair(w, p);});
	for (const auto& weightProfit : v)
	{
		int weight, profit;
		best.swap(prev);
		std::tie(weight, profit) = weightProfit;
		if (prev[weight] < profit) {
			best[weight] = profit;
		}
		for (int i = 1; i <= G; ++i)
		{
			if ((i + weight) <= G && prev[i] && ( (prev[i] + profit) > prev[i + weight]))
			{
				best[i + weight] = prev[i] + profit;
			}
			if (best[i] < prev[i])
			{
				best[i] = prev[i];
			}
		}
	}
	int res = 0;
	for (const auto i : best) 
		if (i > res) res = i;
	fm << res;
	return 0;
}