#include <iostream>
#include <fstream>

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

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

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

short n;
short castig[10005];
long long int w;
long long int greutate[10005];


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

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

void adaugareElement(long long int val,long long int 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)
                    {
                     if(L2.prim==L2.ultim)
                        {
                         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++;
        }
}

void stergereLista(Llin Lista)
{
    nod *r=Lista.prim;
    while(r!=NULL)
        {
         nod *t=r->succ;
         delete r;
         r=t;
        }
}

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

    L1.prim= new nod;
    L1.prim->info=0;
    L1.prim->li=0;
    L1.prim->ls=greutate[1]-1;
    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->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(long j=0;j<greutate[i];++j)
                {
                 nod *q=determinarePozitieCastig(j);
                 adaugareElement(q->info,j);
                }
             for(long 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);
                }

              stergereLista(L1);
              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;*/
            }
        }
    fout<<L1.ultim->info<<"\n";
    return 0;
}