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

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

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&N,&G);
	for(i=1;i<=N;i++)scanf("%d%d",&W[i],&P[i]);
}

void solve()
{
	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);
}