def sac(E,P):
    temp = [ [0] * (P+1) for i in range( len(E)+1 )]
    garde  = [ [False] * (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:
                if E[i-1][1] + temp[i-1][p-E[i-1][0]] > temp[i-1][p]:
                    temp[i][p] =  E[i-1][1] + temp[i-1][ p - E[i-1][0] ]
                    garde[i][p] = True
                else:
                    temp[i][p] = temp[i-1][p]
    p,L = P,[]
    for i in range(len(E),0,-1):
        if garde[i][p]:
            L.append(i)
            p -= E[i-1][0]

    return temp[len(E)][P] , L