#include<fstream>
using namespace std;

const int kNMax = 5005, kGMax = 10005;
int n, g, greutate[kNMax], pret[kNMax], optim[kGMax], sol;

void Citire() {
    ifstream in("rucsac.in");
    in >> n >> g;
    for (int i = 1; i <= n; ++i)
        in >> greutate[i] >> pret[i];
    in.close();
}

void Solve() {
    for (int i = 1; i <= n; ++i)
        for (int j = g - greutate[i]; j >= 0 ; --j)
            if (optim[j + greutate[i]] < optim[j] + pret[i]) {
                optim[j + greutate[i]] = optim[j] + pret[i];
                sol = max(sol, optim[j + greutate[i]]);
            }
}

void Afisare() {
    ofstream out("rucsac.out");
    out << sol << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}