#include <fstream>
#include <algorithm>

using namespace std;

#define INFILE "rucsac.in"
#define OUTFILE "rucsac.out"
#define ll long long
#define VMAX 5002
#define GMAX 10001

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n, g, w[VMAX], p[VMAX];
ll v[GMAX];

void solve(){

    fin >> n >> g;

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

    for(int i = 1; i <= n; ++i){
        for(int j = g; j >= w[i]; --j){

            v[j] = max(v[j], v[j - w[i]] + p[i]);

        }
    }

    fout << v[g] << '\n';

}

int main(){
    solve();
    return 0;
}