#include <fstream>

using namespace std;

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

const int n=5000;
const int g=10000;
int P[n + 1],W[n + 1],profit[g + 1];

int main() {
    int N, G;
    in >> N >> G;
    for (int i = 0; i < N; i++) {
        in >> W[i] >> P[i];
    }

    for (int i = 1; i <= G; i++) {
        profit[i] = -1;
    }
    profit[0] = 0;

    for (int i = 0; i < N; i++) {
        for (int j = G - W[i]; j >= 0; j--) {
            if (profit[j] != -1 && profit[j] + P[i] > profit[j + W[i]]) {
                profit[j + W[i]] = profit[j] + P[i];
            }
        }
    }

    int maxim = -1;
    for (int i = 0; i <= G; i++) {
        if (profit[i] > maxim) {
            maxim = profit[i];
        }
    }
    out << maxim;
    return 0;
}