#include <iostream>
#define NMax 5001
#define MaxG 10001
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,GMax,Greutate[NMax],Valoare[NMax],CMax[NMax],Uz[MaxG][NMax];

void Citire()
{
    int i;
    fin>>n>>GMax;
    for(i=1;i<=n;i++)
        fin>>Greutate[i]>>Valoare[i];
}

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(Greutate[i]<=S && CMax[S-Greutate[i]]!=-1 && !Uz[S-Greutate[i]][i])
                if(CMax[S]<Valoare[i]+CMax[S-Greutate[i]])
                {
                    CMax[S]=Valoare[i]+CMax[S-Greutate[i]];
                    for(k=1;k<=n;k++)
                        Uz[S][k]=Uz[S-Greutate[i]][k];
                    Uz[S][i]=1;
                }
}

int main()
{
    Citire();
    Dinamica();
    fout<<CMax[GMax];
    return 0;
}