#include<algorithm>
#include<fstream>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
pair<int ,int> v[5005];
int f[10005], g;
int n,i,j,k,maxi;

int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;
    sort(v+1, v+1+n);
    //for(i=1;i<=n;i++)
        //fout<<v[i].first<<" "<<v[i].second<<"\n";
    f[0]=1;
    for(i=1;i<=n;i++)
    {
        for(j=g;j>=0;j--)
        {
            //fout<<f[j]<<" ";
            if(f[j]>0&&j+v[i].first<=g)
            {
                f[v[i].first+j]=max(f[v[i].first+j],f[j]+v[i].second);
                if(f[j]+v[i].second>maxi)
                    maxi=f[j]+v[i].second;
            }
        }
    }
    fout<<maxi-1;
    fin.close();
    fout.close();
    return 0;
}