//#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
struct adat
{
    int kg,ar;
};
vector<adat>x;

struct adat2
{
    int ar;
    vector<int>targy;
};
vector<adat2>v;

int maxi,n,g,i,j,a,b,c,m;
int main()

{
    cin>>n>>g;
    x.resize(n+1);
    for(i=1;i<=n;++i)
        cin>>x[i].kg>>x[i].ar;
/*
        for(i=1;i<=n;++i)
            cout<<x[i].kg<<" "<<x[i].ar<<"\n";
*/
    v.resize(g+1);
    for(i=1;i<=n;++i)
    {
        c=x[i].kg;
        if(x[i].kg<=g)
        {
        if(v[x[i].kg].targy.empty())
        {
                v[c].targy.push_back(i);
                v[c].ar=x[i].ar;
        }
        else
        if(!v[x[i].kg].targy.empty())
            if(v[x[i].kg].ar<x[i].ar)
        {
            v[x[i].kg].ar=x[i].ar;
            v[x[i].kg].targy.clear();
            v[x[i].kg].targy.push_back(i);
        }
        if(i>1)
        {
            for(j=v.size()-1;j>=1;--j)
              if(v[j].ar!=0 && (j!=x[i].kg || v[j].targy[0]!=i))
               {
                       b=j+x[i].kg;
                if(v[b].targy.empty())
                {
                     v[b].targy=v[j].targy;
                       v[b].targy.push_back(i);
                       v[b].ar=x[i].ar+v[j].ar;
                }

                else if(v[b].ar>v[j].ar)
                   {
                       v[b].targy.clear();
                       v[b].targy=v[j].targy;
                       v[b].targy.push_back(i);
                       /*for(a=0;a<v[i].targy.size()+1;++a)
                        v[b].targy.push_back(v[a].targy);
                        */
                        v[b].ar=x[i].ar+v[j].ar;
                   }
               }
        }
        }
    }
   /* for(i=1;i<v.size();++i)
    {
        for(j=0;j<v[i].targy.size();++j)
            cout<<v[i].targy[j]<<" ";
        cout<<" "<<v[i].ar<<"\n";
    }
*/
    for(i=1;i<v.size();++i)
    {
        if(v[i].ar>maxi) maxi=v[i].ar;
    }
    cout<<maxi;
    return 0;
}