#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gmx,i,val[20001],q[10001],v[10001],x,y,mx,j,sol,m[1000][1000],i1;
int main()
{
    f>>n>>gmx;
    for(i=1;i<=n;i++)
           f>>q[i]>>v[i];
    for(i=1;i<=n;i++)
    for(j=mx;j>=0;j--)
    {
        if(val[j+q[i]]<val[j]+v[i]&&j+q[i]<=gmx&&(!j||val[j]))
         {
            for(i1=1;i1<=n;i1++) m[j+q[i]][i1]=m[j][i1];
            m[j+q[i]][i]=1;
            val[j+q[i]]=val[j]+v[i];
            if(q[i]+j>mx) mx=q[i]+j;
        }
    }
    sol=0;
    for(i=0;i<=gmx;i++)
        if(sol<val[i]) sol=val[i];
    g<<sol<<'\n';
   /* for(i=1;i<=n;i++)
        if(m[mx][i]==1) g<<i<<' ';*/
    return 0;
}