#include <fstream>

using namespace std;

int d[2][10010], W[5010], P[5010];
int main(){
    int N, G, i, w, l;

    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");

    fin >> N >> G;
    for(i = 1; i <= N; i++)
        fin >> W[i] >> P[i];

    l = 0;
    for(i = 1; i <= N; i++, l = 1 - l){
        for(w = 0; w <= G; w++) {
            d[1 - l][w] = d[l][w];
            if(W[i] <= w)
                d[1 - l][w] = max(d[1 - l][w], d[l][w - W[i]] + P[i]);
        }
    }
    fout << d[l][G];
    return 0;
}