#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int N, Gmax;
vector<int> Weight, Profit;
vector<vector<int> > Sol;

int main() {

    int i, line, curr_weight;

    f >> N >> Gmax;

    Weight.resize(N+1);
    Profit.resize(N+1);
    Sol.resize(2, vector<int>(Gmax+1, 0));

    for(i=1; i<=N; ++i)
        f >> Weight[i] >> Profit[i];

    for(i=1, line=0; i<=N; ++i, line=1-line)
        for(curr_weight=0; curr_weight<=Gmax; ++curr_weight) {
            Sol[1-line][curr_weight] = Sol[line][curr_weight];
            if(Weight[i] <= curr_weight)
                Sol[1-line][curr_weight] = max(Sol[1-line][curr_weight], Sol[line][curr_weight - Weight[i]] + Profit[i]);
        }

    g << Sol[line][Gmax] << "\n";

    f.close();
    g.close();
}