#include <fstream>

using namespace std;

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

unsigned int m[WMAX][2] = {{},{}};

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();

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

    g<<m[G][1]<<'\n';
    g.close();

    return 0;
}