#include <iostream>
#include <fstream>

using namespace std;

const int MAX_N = 5100;
const int MAX_G = 10010;

int maxim, n, g, opt[MAX_G], p[MAX_N], w[MAX_N];
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
void solve();

int main(){


    fin >> n >> g;

    for(int i=1; i<=n; i++){
        fin >> w[i] >> p[i];
    }

    solve();

    fout << maxim;
    fout.close();
    fin.close();
return 0;
}

void solve(){
    for(int i=1; i<=n; i++){
        for(int j=g-w[i]; j>=0; j--){
            if(opt[j+w[i]]<opt[j]+p[i])
                opt[j+w[i]] = opt[j]+p[i];

            if(maxim < opt[j+w[i]] ) maxim = opt[j+w[i]];
        }

    }

}