#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

struct nod{
    long long int info;
    nod *pred;
    nod *succ;
};

struct Llin
    {
     nod *prim,*ultim;
    }L;

int n;
int castig[5005];
long w;
long greutate[5005];

long determinareCastigMaxim(long l,long c)
{
    if(l==0 || c==0) return 0;
     else
        {
         if( (c < greutate[l]) || (greutate[l] > w) ) return determinareCastigMaxim(l-1,c);
          else return max( castig[l]+determinareCastigMaxim(l-1,c-greutate[l]), determinareCastigMaxim(l-1,c) );
        }
}

int main()
{
    fin>>n>>w;
    for(long i=1;i<=n;++i) fin>>greutate[i]>>castig[i];

    //cout<<determinareCastigMaxim(n,w)<<"\n";

    L.prim= new nod;
    L.prim->info=0;
    L.prim->succ=NULL;
    L.prim->pred=NULL;
    L.ultim=L.prim;
    for(long i=1;i<=w;++i)
        {
         nod *p=new nod;
         if(i<greutate[1]) p->info=0;
          else p->info=castig[1];
         p->succ=NULL;
         p->pred=NULL;
         p->pred=L.ultim;
         L.ultim->succ=p;
         L.ultim=p;
        }

    for(long i=2;i<=n;++i)
        {
         if(greutate[i]<=w)
            {
             nod *p=L.ultim;
             long k=w;
             while(p!=NULL)
                {
                 if(k >= greutate[i])
                    {
                     long j=k;
                     nod *q=p;
                     while(j>k-greutate[i])
                        {
                         q=q->pred;
                         j--;
                        }
                     if(castig[i]+q->info > p->info) p->info=castig[i]+q->info;
                    }
                 k--;
                 p=p->pred;
                }
            }
        }
    fout<<L.ultim->info<<"\n";
    return 0;
}