#include <fstream>

struct Obj {
    int val, wei;
    Obj() {
    }
    Obj(int a, int b) : val(a), wei(b) {
    }
};

int main() {

    std::ifstream in("rucsac.in");
    std::ofstream out("rucsac.out");

    int nV, nG;
    in >> nV >> nG;

    Obj *Arr = new Obj[nV + 1];
    for(int i = 1; i <= nV; i++) {
        int a, b;
        in >> a >> b;
        Arr[i] = Obj(a, b);
    }

    int **B = new int*[2];
    for(int i = 0; i < 2; i++) {
        B[i] = new int[nG + 1];
    }

    for(int j = 0; j <= nG; j++) {
        B[0][j] = 0;
    }

    int l = 0;
    for(int i = 1; i <= nV; i++, l = 1 - l) {
        for(int j = 0; j <= nG + 1; j++) {
            B[1 - l][j] = B[l][j];
            if(Arr[i].wei <= j) {
                if(Arr[i].val + B[l][j - Arr[i].wei] > B[1 - l][j]) {
                    B[1 - l][j] = Arr[i].val + B[l][j - Arr[i].wei];
                }
            }
        }
    }

    out << B[l][nG];

    return 0;
}