//care nai ce face si copiezi coduri???
//hai, glumeam, poti sa te uiti, da fao singur, nu copia, te va ajuta mai mult
#include<fstream>
#include<algorithm>
using namespace std;
int greut[5000], euro[5000], n, g, val[5000], sume[5000], sol, pozitie;
ifstream fin( "rucsac.in");
ofstream fout("rucsac.out");
inline void citire()
{
    fin >> n >> g;
    for(int i = 0; i < n; ++i)
    {
        fin >> greut[i];
        fin >> euro[i];
    }
}
int main()
{
    citire();
    sume[greut[0]] = greut[0];
    val[greut[0]] = euro[0];
    for(int i = 1; i < n; ++i)
    {
//        if(val[greut[i]] < euro[i])
//        {
//            val[greut[i]] = euro[i];
//            sume[greut[i]] = greut[i];
//        }
        for(int j = g - greut[i]; j >= 0; --j)
        {
            //if (sume[j])
            {
                pozitie = j + greut[i];

//                val [pozitie ] = max(val[pozitie ], val[j] + euro[i]);
                if(val[pozitie ] <  val[j] + euro[i])
                {
                    val[pozitie ] = val[j] + euro[i];
                    sume[pozitie ] = greut[i];
                }
                sol = max(sol, val[pozitie]);
//                if (sol == 23)
//                {
//sol--;sol++;
//                }
            }
        }
    }
    fout << sol;
    return 0;
}