# include <fstream>
using namespace std;
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++)
	{
		if (k%2==1)
			{
				i=1;
				q=1;
			}
			else
			{
				i=2;
				q=-1;
			}
		
		for (j=1;j<=gr;j++)
		{
			
			
			if (j>=g[k])
				if (a[i+q][j-g[k]]+p[k]>a[i+q][j])
					a[i][j]=a[i+q][j-g[k]]+p[k];
				else
					a[i][j]=a[i+q][j];
				
			else
				a[i][j]=a[i+q][j];
			
		}
	}
		if (n%2)
			gout<<a[1][gr];
		else
			gout<<a[2][gr];
		
		return 0;
}