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))