# include <fstream>

using namespace std;
#define max(a,b) (a>b? a:b)
ifstream f ("rucsac.in");
ofstream gout ("rucsac.out");
int a[3][10005],g[5005],p[5005],i,j,n,k,q,gr;


int main ()
{
	f>>n>>gr;
	for (i=1;i<=n;i++)
		f>>g[i]>>p[i];
	
	for (k=1;k<=n;k++)
	{
		k%2==1 ? i=q=1:i=(q=-1)*-2;
			
		
		for (j=1;j<=gr;j++)
			j>=g[k] ? a[i][j]=max (a[i+q][j-g[k]]+p[k],a[i+q][j]):a[i][j]=a[i+q][j];
	}
		if (n%2)
			gout<<a[1][gr];
		else
			gout<<a[2][gr];
		
		return 0;
}