#include <iostream>
#include <fstream>

using namespace std;

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

int n, gr, w[5005], p[5005], dp[10010], maxim;

int main()
{
    f >> n >> gr;
    for (int i = 1; i <= n; ++i) {
        f >> w[i] >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = gr - w[i]; j >= 0; --j) {
            dp[j + w[i]] = max(dp[j + w[i]], p[i] + dp[j]);
            maxim = max(maxim, dp[j + w[i]]);
        }
    }
    g << maxim;
    return 0;
}