#include <fstream>
#include <vector>

int Max_Profit(std::vector<int> W,std::vector<int> P, std::vector<int>& DP , int G, int N)
{
	for(int i = 1; i<N+1;i++)
	{
		for(int j = G; j >= 0 ; j--)
		{
			if(W[i-1] <= j)
			{
				DP[j] = std::max(DP[j], DP[j - W[i - 1]] + P[i - 1]);
			}
		}
	}

	return DP[G];
}

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

	std::vector<int> W, P;

	int n, G;
	fin >> n >> G;
	std::vector<int> DP(G+1 , 0);
	for(int i = 0; i < n; i++)
	{
		int w, p;
		fin >> w >> p;
		W.push_back(w);
		P.push_back(p);
	}

	fout << Max_Profit(W, P, DP, G, n);


}