#include <fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
#define N 5001
struct date
{
    int profit;
    bool uz[N];
}optim[N];

bool verif();

int n,G,w[N],p[N],i,g,j,profit,poz;

int main()
{
    fin>>n>>G;
    for (i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    for (g=1;g<=G;g++)
    {
        poz=0;
        for (i=1;i<=n;i++)
        {
            profit=(w[i]<=g?optim[g-w[i]].profit+p[i]:0);
            if (verif())
            {
                optim[g].profit=profit;
                poz=i;
            }
        }
        for (j=1;j<=n;j++)
            optim[g].uz[j]=optim[g-w[poz]].uz[j];
        optim[g].uz[poz]=1;
    }
    fout<<optim[G].profit<<'\n';
    fout.close();
    return 0;
}

bool verif()
{
    return profit+optim[g-w[i]].profit>optim[g-w[i]].profit && !optim[g-w[i]].uz[i];
}