#include <fstream>
using namespace std;

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

    int n, g;
    fin >> n >> g;

    int *w = new int[n];
    int *p = new int[n];

    for (int i = 0; i < n; ++i)
        fin >> w[i] >> p[i];

    int *d = new int[g+1];

    for (int i = 0; i <= g; ++i)
        d[i] = 0;

    for (int i = 1; i <= n; ++i) {
        int wi = w[i-1];
        int pi = p[i-1];

        for (int cw = g; cw >= 0; --cw)
            if (wi <= cw)
                d[cw] = max(d[cw], d[cw-wi]+pi);
    }

    int res = 0;
    for (int i = 0; i <= g; ++i)
        res = max(res, d[i]);

    fout << res << endl;

    delete[] d;
    delete[] p;
    delete[] w;
    return 0;
}