#include<fstream>
using namespace std;

int n,g,greutate[5001], pret[5001],optim[10001],sol;

void citire() {

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

}

void solve() {

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

void afisare() {

    ofstream out("rucsac.out");
    out<<sol<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}