#include <fstream>


// MAIN
int main(int argc, char *argv[]) {
    // VARIABILE
    int n, g;
    int weight, price;
    int v[2][10001] = { 0 };


    // REZOLVARE
    std::ifstream fin("rucsac.in");
    std::ofstream fout("rucsac.out");
    fin >> n >> g;
    for (int cnt = 1; cnt <= n; cnt++) {
        fin >> weight >> price;
        for (int i = 1; i <= g; i++) {
            if (weight > i) {
                v[1][i] = v[0][i];
            } else {
                v[1][i] = std::max(v[0][i], price + v[0][i - weight]);
            }
        }
        for (int j = 1; j <= g; j++) {
            v[0][j] = v[1][j];
        }
    }
    fin.close();

    // AFISARE
    fout << v[0][g];
    fout.close();
    return 0;
}