#include<fstream>
#define maxim(a,b)((a>b) ? a : b)
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int g[5001],c[5001],mat[3][10001];
int main()
{
	int i,j,k,l,n,gr,u,f,a;
	in>>n>>gr;
	for(i=1;i<=n;i++)
		in>>g[i]>>c[i];
	a=1;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=gr;j++)
		{
			if(i%3==0)
			{
				if(g[i]<=j)
					mat[0][j]=maxim(mat[2][j],(mat[2][j-g[i]]+c[i]));
				else
					mat[0][j]=mat[2][j];
			}
			else
				if(i%3==1)
				{
					if(g[i]<=j)
					mat[1][j]=maxim(mat[0][j],(mat[0][j-g[i]]+c[i]));
				else
					mat[1][j]=mat[0][j];
				}
				else
					if(i%3==2)
					{
						if(g[i]<=j)
							mat[2][j]=maxim(mat[1][j],(mat[1][j-g[i]]+c[i]));
					else
						mat[2][j]=mat[1][j];
					}
		}
	}
	out<<mat[n%3][gr];	
	return 0;
}