#include <fstream>
#include <vector>

using namespace std;

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

struct cica
{
    int ar;
    vector <int> sor;
};

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].sor.push_back(i);
        }

        for(j=g-a;j>=1;--j)
        {
            nincs=true;
            for(auto e:zsak[j].sor)
                if(e==i)
                {
                    nincs=false;
                    break;
                }
            if(nincs)
            {
                if(zsak[j].ar+b>=zsak[a+j].ar)
                {
                    zsak[a+j].ar=zsak[j].ar+b;
                    zsak[a+j].sor.clear();
                    for(auto e:zsak[j].sor)
                        zsak[a+j].sor.push_back(e);

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

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

    cout<<maxi;
    return 0;
}