#include <fstream>

using namespace std;

#define VMAX 5001 //dimensiunea vectorului de obiecte.
#define WMAX 10001 //dimensiunea vectorului ce retine greutatile obiectelor.

///VMAX * WMAX = dimensiunea matricei pe baza careia vom afla rezultatul final.
unsigned int m[VMAX][WMAX] = {{},{}};

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    unsigned int v[VMAX] = {},w[WMAX] = {};
    unsigned int N,G,i,cw;

    f>>N>>G; //N - nr obiecte; G - suma greutatilor obiectelor.
    for(i=1;i<=N;i++) f>>w[i]>>v[i]; //v - vectorul ce retine profitul obiectelor.
                                     //w - vectorul ce retine greutatea obiectelor.
    f.close();

    ///Rezolvarea problemei propriu-zise :

    for(i = 1; i<= N; i++) {
      for(cw = 0; cw <= G; cw++) {
        m[i][cw] = m[i-1][cw];
        if(w[i] <= cw) {
          //Adaugam profitul v[i] la solutia m[i][cw].
          m[i][cw] = max(m[i][cw],m[i-1][cw - w[i]] + v[i]);
        }
      }
    }

    //Afisam solutia este reprezentata de ultimul element al matricei si anume m[N][G].
    g<<m[N][G]<<'\n';
    g.close();

    return 0;
}