def sac(E,P,i):

    if i == 0: return 0

    if E[i-1][0] > P: return sac(E , P , i-1)

    else: return max( sac(E , P , i-1) , E[i-1][1] +

                    sac(E , P-E[i-1][0] , i-1) )



def initSac(E,P):

    return sac(E , P , len(E))