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

using namespace std;

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


int N, G;
int dp[3][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(){
    int l = 1;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= G; ++j){
            dp[1 - l][j] = dp[l][j];
            if(gr[i - 1] <= j){
                dp[1 - l][j] = max(dp[1 - l][j], dp[l][j - gr[i - 1]] + vl[i - 1]);
            }
        }
        if(l == 1)
            l = 0;
        else
            l = 1;
    }
    out << dp[l][G] << "\n";
}


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