#include <fstream>
#include <vector>
#define NMAX 5000
using namespace std;

struct obiect {
    int g, val;
}v[NMAX];
int N, G;

void citire() {
    ifstream in("rucsac.in");
    in>>N>>G;
    for (int i=0; i<N; ++i) {
        in>>v[i].g>>v[i].val;
    }
    in.close();
}

int dinamica() {
    vector<int> dyn(G+1, -1);
    dyn[0] = 0;
    int pos = 0, MAX = 0;
    for (int i=0; i<N; ++i) {
        for (int j=pos; j>=0; --j) {
            if (dyn[j] >= 0) {
                if ((j + v[i].g <= G) && (dyn[j] + v[i].val > dyn[j + v[i].g])) {
                    dyn[j + v[i].g] = dyn[j] + v[i].val;
                    if (dyn[j + v[i].g] > MAX) {
                        MAX = dyn[j + v[i].g];
                    }
                    if (j + v[i].g > pos) {
                        pos = j + v[i].g;
                    }
                }
            }
        }
    }
    return MAX;
}

void afisare() {
    ofstream out("rucsac.out");
    out<<dinamica();
    out.close();
}

int main() {
    citire();
    afisare();
    return 0;
}