# 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++)
	{
			
		
		for (j=1;j<=gr;j++)
			if (k%2==0)
			j>=g[k] ? a[2][j]=max (a[1][j-g[k]]+p[k],a[1][j]):a[2][j]=a[1][j];
			else
				j>=g[k] ? a[1][j]=max (a[2][j-g[k]]+p[k],a[2][j]):a[1][j]=a[2][j];
	}
		if (n%2)
			gout<<a[1][gr];
		else
			gout<<a[2][gr];
		
		return 0;
}