#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, G, w[5005], p[5005], sol, best[10005];

int main()
{
    f>>n>>G;
    for (int i=1; i<=n; ++i) f>>w[i]>>p[i];

    for (int i=1; i<=n; ++i)
        for (int j=G-w[i]; j>=0; --j)
            if (best[j+w[i]]<best[j]+p[i])
            {
                best[j+w[i]]=best[j]+p[i];
                if (best[j+w[i]]>sol) sol=best[j+w[i]];
            }
    g<<sol<<'\n';
    return 0;
}