#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>(N + 1, 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++) {
        for (int i = 1; i <= G; i++) {
            partial.at(i).at(j) = max(partial.at(i).at(j) , partial.at(i).at(j-1));
            if (i >= weight.at(j - 1)) {
                partial.at(i).at(j) = max(partial.at(i).at(j), profit.at(j - 1));
                partial.at(i).at(j) = max(partial.at(i).at(j), profit.at(j - 1) + partial.at(i - weight.at(j - 1)).at(j-1));
            }
        }
    }
    f2 << partial[G][N];
    f1.close();
    f2.close();
    return 0;
}