#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 5001;
const int INFI = 0x3f3f3f3f;
int Gmax, N;
int g[NMAX], p[NMAX];
int memo[2][2 * NMAX];

int rucsac_memo(int i, int Gramas){
    if(i == 0){
        return 0;
    }

    if(memo[i][Gramas] != INFI){
        return memo[i][Gramas];
    }

    int profit_skip_obj = rucsac_memo(i - 1, Gramas);

    int profit_luat_obj = 0;
    if(g[i] <= Gramas){
        profit_luat_obj = p[i] + rucsac_memo(i - 1, Gramas - g[i]);
    }

    int ans;
    if(profit_skip_obj > profit_luat_obj){
        ans = profit_skip_obj;
    }else{
        ans = profit_luat_obj;
    }
    memo[i][Gramas] = ans;
    return memo[i][Gramas];
}

void rucsac_bottom_up(){
    for(int i = 1; i <= N; i++){
        for(int gc = 0; gc <= Gmax; gc++){
            /// 1. Decizia de a nu lua obiectul
            memo[i][gc] = memo[i - 1][gc];

            /// 2. Luam obiectul daca putem cu greutatea curenta
            if(gc >= g[i]){
                memo[i][gc] = max(memo[i][gc], p[i] + memo[i - 1][gc - g[i]]);
            }
        }
    }
}

void rucsac_two_lines(){
    for(int i = 1; i <= N; i++){
        int l = i % 2;
        for(int gc = 0; gc <= Gmax; gc++){
            /// 1. Decizia de a nu lua obiectul
            memo[l][gc] = memo[1 - l][gc];

            /// 2. Luam obiectul daca putem cu greutatea curenta
            if(gc >= g[i]){
                memo[l][gc] = max(memo[l][gc], p[i] + memo[1 - l][gc - g[i]]);
            }
        }
    }
}

int main()
{
    fin >> N >> Gmax;
    for(int i = 1; i <= N; i++){
        fin >> g[i] >> p[i];
    }
//    for(int i = 1; i <= N; i++){
//        for(int j = 1; j <= Gmax; j++){
//            memo[i][j] = INFI;
//        }
//    }
    /// rucsac_bottom_up(); /// change also memo size
//    for(int i = 1; i <= N; i++){
//        for(int j = 0; j <= Gmax; j++){
//            cout << memo[i][j] << " ";
//        }
//        cout << "\n";
//    }
  ///  fout << memo[N][Gmax];

    rucsac_two_lines();
    fout << memo[N % 2][Gmax];
    return 0;
}