#include<fstream>
using namespace std;
fstream f,h;
int c[5000],g[5000],CMax[5000],Uz[5000][5000],n,GMax;//ATENTIEEEE
void citire()
{
    f.open("rucsac.in",ios::in);
    int i,j;
    f>>n>>GMax;
    for(i=1; i<=n; i++)
        f>>g[i]>>c[i];
}
void rezolvare()
{
    int S,k,i;
    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 afisare()
{
    h.open("rucsac.out",ios::out);
    h<<CMax[GMax];
}
int main()
{
    citire();
    rezolvare();
    afisare();
}