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]