#include<fstream>
using namespace std;
int Gmax,n,s,Cmax[5001],g[5001],c[5001],uz[1000][1000];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void citire()
{
    int i;
    fin>>n>>Gmax;
    for(i=1;i<=n;i++)fin>>g[i]>>c[i];
    fin.close();
}
void dinamica()
{
    int S,i,k;
    for(S=1;S<=Gmax;S++)Cmax[S]=-1;
    for(S=1;S<=Gmax;S++)
        for(i=1;i<=n;i++)
            if(g[i]<=S&&Cmax[S-g[i]]!=-1&&!uz[S-g[i]][i])
                if(Cmax[S]<c[i]+Cmax[S-g[i]])
                {
                    Cmax[S]=c[i]+Cmax[S-g[i]];
                    for(k=1;k<=n;k++)
                        uz[S][k]=uz[S-g[i]][k];
                    uz[S][i]=1;
                }
}
void afis()
{
   fout<<Cmax[Gmax];
}
int main()
{
    citire();
    dinamica();
    afis();
    fout.close();
    return 0;
}