#include <fstream>
#define NMAX 5001
#define GMAX 10001
using namespace std;

struct obiect
{   int gr, val;
} v[NMAX];

int n, G, i, j, a[GMAX], gmax, maxi;

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

int main()
{   f>>n>>G;
    for (i=1; i<=n; ++i)
        f>>v[i].gr>>v[i].val;
    a[0]=1;
    for (i=1; i<=n; ++i)
    {   for (j=gmax; j>=0; --j)
            if (a[j] && j+v[i].gr<=G && a[j+v[i].gr]<a[j]+v[i].val)
            {   a[j+v[i].gr]=a[j]+v[i].val;
                if (j+v[i].gr>gmax)
                    gmax=j+v[i].gr;
                maxi=max(maxi, a[j+v[i].gr]);
            }
    }
    g<<maxi-1<<'\n';
    return 0;
}