#include <fstream>

using namespace std;

//Variabilele globale:
//m - matricea pe care facem dinamica
//g, p - vectorii cu greutatile, resprectiv preturile
unsigned short/*long int*/ n,G,g[10001],p[5001];
unsigned long int m[2][10001];

//Functia care determina maximul
unsigned short max(unsigned short int a,unsigned short int b)
{
    if(a>b)
		return a;
    return b;
}

int main()
{
	//Dechiderea fisierelor
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	
	//Declararea contoarelor
	unsigned short int i=1,j=0;
	
	//Citirea numarului de obiecte si a capacitatii rucsacului 
    fin>>n;
	fin>>G;

	//Citirea obiectelor
    for(;i<=n;i++)
    {
        fin>>g[i];
        fin>>p[i];
    }
	
	//Variabila folosita pentru a alterna liniile
	unsigned short int h=1;
	
	//Dinamica in O(N*G) si O(2*G) memorie
	for(i=n;i>=1;i--,h=1-h)
	{
		for(j=0;j<=G;j++)
		{
			if(j>=g[i])
			{
				m[h][j]=max(m[1-h][j],m[1-h][j-g[i]]+p[i]);
			}
			else
			{
				m[h][j]=m[1-h][j];
			}
		}
	}
	
	//Afisarea raspunsului
	fout<<m[1-h][G]<<'\n';
	
	//Incheiere
	fin.close();
	fout.close();
	
	return 0;
}