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

using namespace std;

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

unsigned int m[5000][10000];

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

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