#include<fstream>
using namespace std;
int greutate[5001], pret[5001],optim[10001],n,g,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 rucsac() {

    int i,j,p;
    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();
    rucsac();
    afisare();

    return 0;
}