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

using namespace std;

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

struct Obiect {
    unsigned int greutate;
    unsigned int valoare;
};

int main() {
    unsigned int N, G, i, j;
    fin >> N >> G;
    vector<Obiect> p(N);
    vector<unsigned int> vechi(G+1), nou(G+1);
    for(i=0; i<N; ++i) {
        fin >> p[i].greutate >> p[i].valoare;
    }
    for(j=0; j<p[0].greutate; ++j) {
        vechi[j] = 0;
    }
    for(j=p[0].greutate; j<=G; ++j) {
        vechi[j] = p[0].valoare;
    }
    for(i=1; i<N; ++i) {
        for(j=0; j<p[i].greutate; ++j) {
            nou[j] = vechi[j];                             // obiectul nu mai încape, deci valoarea rămâne
        }
        for(j=p[i].greutate; j<=G; ++j) {
            nou[j] = max(
                vechi[j],                                   // nu luăm obiectul
                vechi[j - p[i].greutate] + p[i].valoare     // luăm obiectul
            );
        }
        // Copiem în vectorul vechi
        for(j=0; j<=G; ++j) {
            vechi[j] = nou[j];
        }
    }
    fout << nou[G] << endl;
    return 0;
}