#include <fstream>

using namespace std;

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

const int Nmax = 5005;
const int Gmax = 10005;

int n, greutate_max;
long long dp[2][Gmax];

void citire_parametrii(){
    fin >> n >> greutate_max;
}

void citire_si_procesare_obiecte(){
    int val, greutate;
    bool poz, prev_poz;

    dp[0][0] = dp[1][0] = 0;

    for(int i = 1; i <= n; i++){
        fin >> greutate >> val;

        poz = i & 1;
        prev_poz = !poz;

        for(int j = 0; j <= greutate_max; j++){
            if(greutate <= j){
                dp[poz][j] = max(dp[prev_poz][j], dp[prev_poz][j - greutate] + val);
            }
            else{
                dp[poz][j] = dp[prev_poz][j];
            }
        }
    }
}

void afisare_profit_maxim(){
    fout << dp[n & 1][greutate_max];
}

int main(){
    citire_parametrii();
    citire_si_procesare_obiecte();

    afisare_profit_maxim();

    return 0;
}