#include<fstream>
//YOOOOOOOOOOOOOOOHHHOOOOOOOOOOOOOOOOOOOOOOO!!!!!!!!!!!!!!!!!!!
//Se pare ca de prost ce is!!, am bagat  |chiar aici sub| si mai inainte memorie insuficienta!!
using namespace std;               //    V              V
int greut[5010], euro[5010],n, g,  /*sume[10010]*/   val[10010], sol, pozitie;//dar ia uite, nnu mai am nevoie de sume, tehehe
//cat de LOL!, cum sa gresec aici!? si ma chinui de 2 zile la debugging!
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();//am mai taiat cate ceeva pe-aciea, mama-mama, tre sa mai lucrez la dinaste, ptiuuuuuu
    sol = 0;
//    sume[greut[0]] = greut[0];
    val[greut[0]] = euro[0];
    for(int i = 0; i < n; ++i)//hihiihi, am uitat un i=0, nu i=1
    {
//        if(val[greut[i]] < euro[i])
//        {
//            val[greut[i]] = euro[i];
////            sume[greut[i]] = greut[i]; //chiar nu inteleg dece mam complicat aicea
//        }
        for(int j = g - greut[i]; j >= 0; --j)
        {
            pozitie = j + greut[i];
//            if (val[j])//si chiar si acici, de fapt vina e pt ca eu am gandito altfel
//                if (pozitie <= g)
            {
                if(val[pozitie ] <  val[j] + euro[i])
                {
                    val[pozitie ] = val[j] + euro[i];
                    if(sol < val[pozitie])
                    {
                        sol = val[pozitie];
                    }
//                    sume[pozitie ] = greut[i];
                }
            }

        }
    }
    fout << sol;
    return 0;
}