#include <fstream>
using namespace std;

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

int main()
{
    int w[5005], p[5005], dp[10005] = {0};

    int n, gr;
    fin >> n >> gr;

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

    for (int i = 1; i <= n; ++i)
        for (int j = gr - w[i]; j >= 0; --j)
            if (p[i] + dp[j] > dp[j + w[i]])
                dp[j + w[i]] = p[i] + dp[j];

    fout << dp[gr];
    return 0;
}