#include <fstream>

struct point
{
    int g,c;
};

point v[5050];

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int a[2][10010],n,g,i,nrmax,ok,p;
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].g>>v[i].c;
        for(p=g;p>=1;p--)
        {
            if (p-v[i].g>=0)
                a[ok][p]=max(a[1-ok][p-v[i].g]+v[i].c,a[1-ok][p]);
            else
                a[ok][p] = a[1-ok][p];
            nrmax=max(nrmax,a[ok][p]);
        }


        ok=1-ok;
    }
    fout<<nrmax;

    return 0;
}