#include <iostream>
#include <fstream>

using namespace std;

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

int n, G, sol;
int g[5005];
int v[5005];
int d[5005]; /// d[i] este valoarea maxima ce se poate obtine cu greutatea i

int main() {
    fin >> n >> G;

    for (int i=1;i<=n;++i)
        fin >> g[i] >> v[i];

    /// initializam toate elementele lui d cu -1
    for (int i=1;i<=n;++i)
        d[i] = -1;

    for (int i=1;i<=n;++i)
        for (int j=G-g[i];j>=0;--j)
            /// pornim de la G-g[i] pentru a nu depasi G
            if (d[j]+1)
                d[j + g[i]] = max(d[j + g[i]], d[j] + v[i]);

    for (int i=1;i<=G;++i)
        sol = max(sol, d[i]);

    fout << sol;
}