#include <fstream>
#include <vector>
#include <map>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

struct cica
{
    int ar;
    vector <int> sor;
    map <int,bool> van;
};

vector <cica> zsak;

int n,i,a,b,g,j;
bool nincs;

int main()
{
    cin>>n>>g;
    zsak.resize(g+1);
    for(i=1;i<=n;++i)
    {
        cin>>a>>b;
        if(zsak[a].ar<=b)
        {
            zsak[a].ar=b;
            zsak[a].sor.clear();
            zsak[a].van.clear();
            zsak[a].sor.push_back(i);
            zsak[a].van[i]=true;
        }

        for(j=g-a;j>=1;--j)
        {
            nincs=true;
            if(zsak[j].van[i]) nincs=false;

            if(nincs && !zsak[j].sor.empty())
            {
                if(zsak[j].ar+b>=zsak[a+j].ar)
                {
                    zsak[a+j].ar=zsak[j].ar+b;
                    zsak[a+j].sor.clear();
                    zsak[a+j].van.clear();

                    for(auto e:zsak[j].sor)
                    {
                        zsak[a+j].sor.push_back(e);
                        zsak[a+j].van[e]=true;
                    }

                    zsak[a+j].sor.push_back(i);
                    zsak[a+j].van[i]=true;
                }
            }
        }
    }

    int maxi=0;
    for(auto e:zsak)
        maxi=max(maxi,e.ar);

    cout<<maxi;
    return 0;
}