#include <fstream>
#include <vector>
#define NMAX 5005
#define GMAX 10005

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");


int N, G;
int dp[NMAX][GMAX];
vector <int> gr;
vector <int> vl;

void Read(){
    int greutate, valoare;
    in >> N >> G;
    for(int i = 0; i < N; ++i){
        in >> greutate >> valoare;
        gr.push_back(greutate);
        vl.push_back(valoare);
    }
}

void Solve(){
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= G; ++j){
            dp[i][j] = dp[i - 1][j];
            if(gr[i - 1] <= j){
                dp[i][j] = max(dp[i][j], dp[i - 1][j - gr[i - 1]] + vl[i - 1]);
            }
        }
    }
    out << dp[N][G] << "\n";
}


int main()
{
    Read();
    Solve();
    return 0;
}