//  Y    Y   EEEEE  Y   Y      ! !
//   Y  Y    E       Y Y       ! !
//    Y      EEEE     Y        ! !
//    Y      E        Y        ! !
//    Y      EEEEE    Y
//                             !!!                                           
//    FFFFF  I   N  N   AAAAAA  L     L     Y   Y
//    F      I   NN N   A    A  L     L      Y Y
//    FFFF   I   N NN   A    A  L     L       Y
//    F      I   N  N   AAAAAA  L     L       Y                ::: DDD
//    F      I   N  N   A    A  L     L       Y                ::: D  D
//    F      i   N  N   A    A  LLLLL LLLLL   Y                ::: D  D
//                                                                 D   D
//            1     0 00        0 00 0                             D   D
//          1 1    0    0      0       0                       ::: D  D
//         1  1   0      0     0         0                     ::: D D
//        1   1  0       0     0         0                     ::: DD
//            1  0       0      0       0
//            1   0     0        0      0
//            1    0000            0 00
//




#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];//oare asta era de bai??? // DDAAAAPPPP !!!!!!!!!!!!!!!! aici sper ca e ULTIMUL BUG CA E-U NU MAI POT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    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;
}