#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gmx,i,val[10001],q[10001],v[10001],x,y,mx,j,sol;
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]))
         {
            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;
    return 0;
}