#include <fstream>
const std::string programName = "rucsac";
std::ifstream f(programName + ".in");
std::ofstream g(programName + ".out");
const int NMAX = 5e3, GMAX = 1e4;
int main() {
    int N, G;
    f >> N >> G;
    int weights[NMAX + 5], profits[NMAX + 5];
    for (int i = 1; i <= N; ++i)
        f >> weights[i] >> profits[i];
    int dynamic[2][GMAX];
    int l = 0;
    for (int i = 1; i <= N; ++i, l ^= 1)
        for (int j = 0; j <= G; ++j) {
                dynamic[1 - l][j] = dynamic[l][j];
            if(weights[i] <= j)
                dynamic[1 - l][j] = std::max(dynamic[1 - l][j], profits[i] + dynamic[l][j - weights[i]]);
        }
    g << dynamic[N & 1][G];
    return 0x0;
}