import collections
import random


def random_sample_with_weight_and_cost(population, weights, costs, cost_limit):
    """
    Like random_sample_with_weight but with the addition of a cost and limit.
    While performing random samples (with priority for higher weight) we'll keep track of cost
    If cost exceeds the cost limit, we stop selecting
    Basically the knapsack problem, but with deliberately random selection rather than dynamic optimization
    """
    population_weights = {request: weight for (request, weight) in zip(population, weights)}
    population_costs = {request: cost for (request, cost) in zip(population, costs)}
    selected = []
    not_selected = []
    cost = 0
    # Create a Counter from the population, assigning count by weight
    counter = collections.Counter(population_weights)
    while counter:
        # Turn the Counter into a list for random selection from
        # The list will have n repetitions of an element with weight n
        choice = random.choice(list(counter.elements()))
        choice_cost = population_costs[choice]
        # If the cost would cause us to exceed our limit it shouldn't be selected
        if cost + choice_cost > cost_limit:
            not_selected.append(choice)
        else:
            cost += choice_cost
            selected.append(choice)
        # When chosen (whether selected or not), remove the element from the population
        # Effectively removes all repetitions of the element
        counter.pop(choice)
    return selected, not_selected