#include <fstream>

using namespace std;

const char InFile[]="rucsac.in";
const char OutFile[]="rucsac.out";
const int MaxG=10111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,G,W,P,sol,buffer1[MaxG],buffer2[MaxG];
int *line1=buffer1,*line2=buffer2;

int main()
{
	fin>>N>>G;
	for(register int i=0;i<N;++i)
	{
		fin>>W>>P;
		for(register int j=0;j<=G;++j)
		{
			line2[j]=line1[j];
			if(j-W>=0)
			{
				if(line2[j]<line1[j-W]+P)
				{
					line2[j]=line1[j-W]+P;
				}
			}
		}
		swap(line1,line2);
	}
	fin.close();
	
	for(register int i=0;i<=G;++i)
	{
		sol=max(sol,line1[i]);
	}
	
	fout<<sol;
	fout.close();
	return 0;
}