#include <fstream>
#include <vector>

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

	int n,g;
	fin>>n>>g;

	std::vector<int> W(n);
	std::vector<int> P(n);

	for(int i=0;i<n;++i) fin>>W[i]>>P[i];



	std::vector<int> optim(g+1);
	for(int i=0;i<n;++i)
		for(int j=g-W[i];j>=0;--j)
			if( optim[j+W[i]] < optim[j] + P[i] )
				optim[j+W[i]]=optim[j]+P[i];

	fout<<optim[g]<<'\n';
}