def sac(E,P):
    temp = [ [0] * (P+1) for i in range(len(E)+1)]
    for i in range(1,len(E)+1):
        for p in range(P+1):
            if E[i-1][0] > p:
                temp[i][p] = temp[i-1][p]
            else:
                temp[i][p] = max(temp[i-1][p], E[i-1][1] + temp[i-1][ p - E[i-1][0] ])
    return temp[len(E)][P]