#include<fstream>
#include<algorithm>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,g,gr[10005],p[5005],a[2][10005],j,i;

main(void)
{
	cin>>n>>g;
	for(i=1;i<=n;++i)cin>>gr[i]>>p[i];
	
	int l=0;
	for(i=1;i<=n;++i,l=1-l)
		for(j=0;j<=g;++j){
			a[1-l][j]=a[l][j];
			if(gr[i]<=j)a[1-l][j]=max(a[1-l][j],a[l][j-gr[i]]+p[i]);
		}
	cout<<a[l][g];
}