#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G;
int W[5008], P[10008];
int d[2][10008];
void init(){
    fin>>n>>G;
    int i;
    for(i=1;i<=n;i++)fin>>W[i]>>P[i];
}
void pd(){
    int ant, crt;
    ant = 1; crt = 0;
    int i, g;
    for(i=1;i<=n;i++){
        for(g=0;g<=G;g++){
            d[crt][g]=d[ant][g];
            if(d[crt][g]<=d[ant][g-W[i]]+P[i]&&W[i]<=g)
                d[crt][g]= d[ant][g-W[i]]+P[i];
        }
        ant=1-ant;crt=1-crt;
    }
}
int main(){
    init();
    pd();
    fout<<d[1][G]<<'\n';
    return 0;
}