#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("date.in");

struct nod{
    long long int info;
    long li,ls,lsactualizat;
    nod *pred;
    nod *succ;
};

struct Llin
    {
     nod *prim,*ultim;
    }L1,L2;

short n;
short castig[10005];
long w;
long greutate[10005];
//short vect[1000000001];

/*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) );
        }
}*/

nod* determinarePozitieCastig(long x)
{
    nod *r=L1.prim;
    while(r->ls<x && r!=NULL)
        r=r->succ;
    return r;
}

nod* cautareCastig(long val)
{
    nod *r=L2.prim;
    while(r->info < val && r->succ!=NULL)
        r=r->succ;
    return r;
}

void adaugareElement(long val,long poz = 0)
{
    if(L2.prim==NULL)
        {
         delete L2.prim;
         L2.prim=new nod;
         L2.prim->info=val;
         L2.prim->li=poz;
         L2.prim->ls=poz;
         L2.prim->succ=NULL;
         L2.prim->pred=NULL;
         L2.ultim=L2.prim;
        }
     else
        {
         nod *v=cautareCastig(val);
         if(v->info!=val)
            {
             nod *t=new nod;
             t->info=val;
             t->li=poz;
             t->ls=poz;
             t->succ=NULL;
             t->pred=NULL;
             if(v==L2.prim)
                {
                /*if(v->info < L2.prim->info)
                    {
                    t->succ=L2.prim;
                    L2.prim=t;
                    }*/
                if(v->info > L2.prim->info)
                    {
                     t->pred=L2.ultim;
                     L2.ultim->succ=t;
                     L2.ultim=t;
                    }
                }
            if(v!=L2.prim && v!=L2.ultim)
                {
                 t->succ=v;
                 t->pred=v->pred;
                 v->pred->succ=t;
                 v->pred=t;
                }
             if(v==L2.ultim)
                {
                 if(val < v->info)
                    {
                     t->succ=v;
                     t->pred=v->pred;
                     v->pred->succ=t;
                     v->pred=t;
                    }
                  else
                    {
                     t->pred=L2.ultim;
                     L2.ultim->succ=t;
                     L2.ultim=t;
                    }
                }
            }
          else v->ls++;
        }
}

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

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

    L1.prim= new nod;
    L1.prim->info=0;
    L1.prim->li=0;
    L1.prim->ls=greutate[1]-1;
    //L1.prim->lsactualizat=0;
    L1.prim->succ=NULL;
    L1.prim->pred=NULL;
    L1.ultim=L1.prim;

    nod *p=new nod;
    p->info=castig[1];
    p->li=greutate[1];
    p->ls=w;
    //p->lsactualizat=0;
    p->succ=NULL;
    p->pred=NULL;
    p->pred=L1.ultim;
    L1.ultim->succ=p;
    L1.ultim=p;

    L2.prim=new nod;
    L2.prim=NULL;

    for(long i=2;i<=n;++i)
        {
         if(greutate[i]<=w)
            {
             for(int j=0;j<greutate[i];++j)
                {
                 nod *q=determinarePozitieCastig(j);
                 adaugareElement(q->info,j);
                }
             for(int j=greutate[i];j<=w;++j)
                {
                 nod *p=determinarePozitieCastig(j-greutate[i]);
                 nod *q=determinarePozitieCastig(j);
                 if(castig[i]+p->info > q->info) adaugareElement(castig[i]+p->info,j);
                  else adaugareElement(q->info,j);
                }

              L1.prim=L2.prim;
              L1.ultim=L2.ultim;
              L2.prim=NULL;
              L2.ultim=NULL;

              /*nod *start=L1.prim;
              while(start!=NULL){
                cout<<start->info<<" "<<start->ls<<" ";
                start=start->succ;
              }
              cout<<endl;*/
            }
        }
    cout<<L1.ultim->info<<"\n";

    /*for(long i=0;i<=w;++i)
        {
         if(i<greutate[1]) vect[i]=0;
          else vect[i]=castig[1];
        }

    for(long i=2;i<=n;++i)
        {
         if(greutate[i]<=w)
            {
             for(long j=w;j>=0;j--)
                {
                 if( j >= greutate[i] && castig[i]+vect[j-greutate[i]] > vect[j] )
                     vect[j]=castig[i]+vect[j-greutate[i]];
                }
            }
        }
    cout<<vect[w]<<"\n";*/
    return 0;
}