///RUCSAC
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream inStr("rucsac.in");
    ofstream outStr("rucsac.out");

    int N, G;
    inStr >> N >> G;

    vector<int> prev(G + 1, 0);
    vector<int> curr(G + 1, 0);
    vector<int> p(N);
    vector<int> w(N);

    for(int i=0; i<N; ++i)
        inStr >> w[i] >> p[i];

    for(int i=0; i<N; ++i) {
        for(int j=1; j<=G; ++j)
            if(w[i] <= j)
                curr[j] = max(prev[j], prev[j - w[i]] + p[i]);
            else
                curr[j] = prev[j];
        swap(prev, curr);
    }

    outStr << prev[G] << '\n';

    return 0;
}