#include <fstream>
#include <algorithm>

using namespace std;
int n,g,w[5001],p[5001],i,v[2][10001],j,k;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f>>n>>g;
    for (i=1;i<=n;i++) f>>w[i]>>p[i];

    k=1;
    for (i=1;i<=n;i++)
        {
            k=1-k;
            for (j=1;j<=g;j++)
                {
                    v[1-k][j]=v[k][j];
                    if (w[i]<j)
                    {
                        v[1-k][j]=max(v[1-k][j],v[k,j-w[i]]+p[i]);
                    }
                }
        }
    k=1-k;
    g<<v[k][g];

    f.close();
    g.close();
    return 0;
}