from typing import Dict


def _sum_expectation_values(
    expectation_values_per_bitstring: Dict[str, float],
    probability_per_bitstring: Dict[str, float],
    alpha: float,
) -> float:
    """Returns the cumulative sum of expectation values until the cumulative probability of bitstrings
    s_k = p(x_1) + … + p(x_k) >= alpha

    Args:
        expectation_values_per_bitstring: dictionary of bitstrings and their corresponding expectation values.
        probability_per_bitstring: dictionary of bitstrings and their corresponding expectation probabilities.
        alpha: see description in the `__call__()` method.
    """
    # Sorts expectation values by values.
    sorted_expectation_values_per_bitstring_list = sorted(
        expectation_values_per_bitstring.items(), key=lambda item: item[1]
    )

    cumulative_prob = 0.0
    cumulative_value = 0.0
    # Sums expectation values for each bitstring, starting from the one with the smallest one.
    # When the cumulative probability associated with these bitstrings is higher than alpha,
    # it stops and effectively discards all the remaining values.
    for bitstring, expectation_value in sorted_expectation_values_per_bitstring_list:
        prob = probability_per_bitstring[bitstring]
        if cumulative_prob + prob < alpha:
            cumulative_prob += prob
            cumulative_value += prob * expectation_value
        else:
            cumulative_value += (alpha - cumulative_prob) * expectation_value
            break
    final_value = cumulative_value / alpha
    return final_value