#include<iostream>
#include<cstdio>
#define maxn 5005
#define maxg 10005
using namespace std;
int T[maxn][maxg],g[maxn],v[maxn],n,G,i,s;
int main()
{
	freopen("rucsac.in","r",stdin);
	freopen("rucsac.out","w",stdout);
	scanf("%d%d",&n,&G);
	for(i=1;i<=n;++i)
		scanf("%d%d",&g[i],&v[i]);
	for(i=1;i<=n;++i)
		for(s=0;s<=G;++s)
			if(g[i]<=s)
				T[i][s]=max(T[i-1][s],T[i-1][s-g[i]]+v[i]);
			else
				T[i][s]=T[i-1][s];
	printf("%d\n",T[n][G]);
	return 0;
}