#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int main() {
    ifstream f1("rucsac.in");
    ofstream f2("rucsac.out");

    int N, G, w, p;
    f1 >> N >> G;

    vector<int> weight;
    vector<int> profit;
    vector<vector<int>> partial(G + 1, vector<int>(2, 0));

    for (int i = 0; i < N; i++) {
        f1 >> w >> p;
        weight.push_back(w);
        profit.push_back(p);
    }

    /*
    for (int i = 0; i < N; i++) {
        partial[weight[i]][i + 1] = profit[i];
    }
    */
    for (int j = 1; j <= N; j++) {
        // clear prev line in marix[G][2]
        for (int i = 1; i <= G; i++) {
            partial.at(i).at(0) = partial.at(i).at(1);
            partial.at(i).at(1) = 0;
        }
        // init profit
        partial.at(weight.at(j - 1)).at(1) = profit.at(j - 1);
        for (int i = 1; i <= G; i++) {
            partial.at(i).at(1) = max(partial.at(i).at(1) , partial.at(i).at(0));
            if (i >= weight.at(j - 1)) {
                partial.at(i).at(1) = max(partial.at(i).at(1), profit.at(j - 1));
                partial.at(i).at(1) = max(partial.at(i).at(1), profit.at(j - 1) + partial.at(i - weight.at(j - 1)).at(0));
            }
        }
    }
    f2 << partial[G][1];
    f1.close();
    f2.close();
    return 0;
}