#include <fstream>
#define MAXN 5010
#define MAXG 10010

using namespace std;

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

int w[MAXG], p[MAXN], n, g, D[2][MAXG];

int main () {
    fin >> n >> g;
    for (int i = 1; i <= n; i++) {
        fin >> w[i] >> p[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int cw = 0; cw <= g; cw++) {
            D[i % 2][cw] = D[(i - 1) % 2][cw];
            if (w[i] <= cw)
                D[i % 2][cw] = max (D[i % 2][cw], D[(i - 1) % 2][cw - w[i]] + p[i]);
        }
    }

    fout << D[n % 2][g];

    return 0;
}