#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 = greutate; j <= greutate_max; j++){
            dp[poz][j] = max(dp[prev_poz][j], dp[prev_poz][j - greutate] + val);
        }
    }
}

void afisare_profit_maxim(){
    long long sol;

    sol = 0;
    for(int i = 1; i <= greutate_max; i++){
        sol = max(sol, dp[n & 1][i]);
    }

    fout << sol;
}

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

    afisare_profit_maxim();

    return 0;
}