#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;
int greut[5000], euro[5000], n, g, 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];
    }
}
//care citesti ma aicea?????????? nai ce face???? ia coppiaza de la altu :P
//TROLOLOLOLOLOLOLOLOLOLOLOLO
int main()
{
    citire();
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    int val[g], sume[g];
    memset(val, 0,g * 4);
    memset(sume, 0, g * 4);
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    sume[greut[0]] = greut[0];
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    val[greut[0]] = euro[0];
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    for(int i = 1; i < n; ++i)
        //TROLOLOLOLOLOLOLOLOLOLOLOLO
    {
        //TROLOLOLOLOLOLOLOLOLOLOLOLO
        for(int j = g - greut[i]; j >= 0; --j)
            //TROLOLOLOLOLOLOLOLOLOLOLOLO
        {
            if (sume[j])
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
            {
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
                pozitie = j + greut[i];
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
                sume[pozitie ] = greut[i];
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
                val [pozitie ] = max(val[pozitie ], val[j] + euro[i]);
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
                sol = max(sol, val[pozitie]);
                //TROLOLOLOLOLOLOLOLOLOLOLOLO
            }
            //TROLOLOLOLOLOLOLOLOLOLOLOLO
        }
        //TROLOLOLOLOLOLOLOLOLOLOLOLO
    }
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    fout << sol;
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
    return 0;
    //TROLOLOLOLOLOLOLOLOLOLOLOLO
}
//TROLOLOLOLOLOLOLOLOLOLOLOLO