#include<cstdio>
#include<bitset>
using namespace std;
#define NM 5005
#define GG 1000005
#define maxim(a,b) (a>b)? (a):(b)
int N,G;
int g[NM],p[NM],rez[GG];
bitset<GG>viz;
inline void read()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&N,&G);
	for (int i=1; i<=N; ++i)
		scanf("%d%d",&g[i],&p[i]);
}
inline void rucsac()
{
	int maxx=0;
	for (int i=1; i<=N; ++i)
	{
		for (int j=G; j-g[i]>=0; --j)
			if (viz[j-g[i]])
			{
				rez[j]=maxim(rez[j],rez[j-g[i]]+p[i]);
				viz[j]=1;
				maxx=maxim(maxx,rez[j]);
			}
		rez[g[i]]=p[i];
		viz[g[i]]=1;
	}
	printf("%d",maxx);
}
int main()
{
	read();
	rucsac();
	return 0;
}