#include <fstream>
using namespace std;
int n, g, p[5005], w[5005], i;
void citire ()
{
    ifstream in ("rucsac.in");
    in >> n >> g;
    for (i = 1; i <= n; ++i)
    in >> w[i] >> p[i];
    in.close ();
}
long long solve ()
{
    int j, optim[10000];
    long long s = 0;
    for (i = 1; i <= n; ++i)
    for (j = g - w[i]; j >= 0; --j)
    if (optim[j+w[i]] < optim[j] + p[i])
    {
        optim[j+w[i]] = optim[j] + p[i];
        if (optim[j + w[i]] > s)
        s = optim[j + w[i]];
    }
    return s;
}
void afis (int sol)
{
    ofstream out ("rucsac.out");
    out << sol << '\n';
    out.close ();
}
int main()
{
    citire ();
    afis (solve ());
    return 0;
}