#include <fstream>
using namespace std;

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

int n, g, i, j, sol, W[10001], P[5001], sum[10001];

int main() {
    fin >> n >> g;
    for (; i < n; ++i)
        fin >> W[i] >> P[i];
    fin.close();
    for (i = 0; i < n; ++i)
        for (j = g - W[i]; j >= 0; --j)
            if (sum[j + W[i]] < sum[j] + P[i]) {
                sum[j + W[i]] = sum[j] + P[i];
                if (sum[j + W[i]] > sol)
                    sol = sum[j + W[i]];
            }
    fout << sol;
    fout.close();
    return 0;
}