#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;

int N,G,i,cw,l,sol,W[5010],P[5010],D[2][10010];

//void read(),solve();

int main()
{
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	//freopen("rucsac.in","r",stdin);
	//freopen("rucsac.out","w",stdout);
	//scanf("%d%d",&N,&G);
	in>>N>>G;
	for(i=1;i<=N;i++)in>>W[i]>>P[i];
		//scanf("%d%d",&W[i],&P[i]);
	for(i=1;i<=N;i++,l=1-l)
	{
		for(cw=0;cw<=G;cw++)
		{
			D[1-l][cw]=D[l][cw];
			if(W[i]<=cw)
				D[1-l][cw]=max(D[l][cw],D[l][cw-W[i]]+P[i]);
		}
	}
	sol=D[l][G];
	//printf("%d\n",sol);
	out<<sol;
	
	return 0;
}