#include <fstream>
#include <cmath>

int dp[2][10005];

int main() {
    std::ifstream fin("rucsac.in");
    std::ofstream fout("rucsac.out");
    int nrn, nrg;
    int wgh, price;
    fin >> nrn >> nrg;
    for(int index = 1; index <= nrn; index++){
        fin >> wgh >> price;
        for(int index2 = 1; index2 < wgh; index2++){
            dp[index & 1][index2] = dp[!(index & 1)][index2];
        }
        for(int index2 = wgh; index2 <= nrg; index2++){
            dp[index & 1][index2] = std::max(dp[!(index & 1)][index2], dp[!(index & 1)][index2 - wgh] + price);
        }
    }
    fout << dp[nrn & 1][nrg];
    return 0;
}