#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int a[5001],b[5001],c[10014],i,j,maxi,g,n,s;
int main(){
	int n;
	in>>n>>g;
	s=0;
	
	for (i=1;i<=n;i++)
	{
		in>>a[i]>>b[i];
	}
	
	for (i=1;i<=10004;i++) c[i]=-1;
	
	c[0]=0;
	
	for (i=1;i<=n;i++)
		for (j=g;j>=0;j--)
		{ 
			if (j+a[i]<=g)
				if (c[j]+b[i]>c[j+a[i]]&&c[j]!=-1) c[j+a[i]]=c[j]+b[i];
		}
	
	i=g; maxi=0;
	
	while (i>=0)
	{
		if (c[i]>maxi) maxi=c[i];
		i--;
	}
	out<<maxi;
    return 0;
}