import random
from math import inf

def alg(demand, supply, depth = 0):
    if not demand: return 0

    (wanted_len, wanted_count) = demand[0]

    indent = "   " * depth
    print(indent + f"Making {demand} with {supply}")

    options = []

    for i, (supply_len, supply_count) in enumerate(supply):
        if supply_len >= wanted_len:
            # copy them for mutation
            new_demand = demand[::]
            new_supply = supply[::]

            add_pipe(wanted_len, -1, new_demand)
            add_pipe(supply_len, -1, new_supply)

            if supply_len > wanted_len:
                add_pipe(supply_len - wanted_len, 1, new_supply)

            options.append(
                alg(new_demand, new_supply, depth + 1)
                + (1 if supply_count == inf else 0))

    res = min(options)
    print(indent + f"Best option is {res} out of {options}")
    return res



def add_pipe(new_pipe_len, amount, to_pipes):
    if amount < -1 or amount > 1: raise Exception("Can add/remove no more than 1 at a time.")
    if new_pipe_len == 0: return

    for i, (pipe_len, pipe_count) in enumerate(to_pipes):
        if new_pipe_len == pipe_len: # perfect match!
            new_amount = pipe_count + amount
            if new_amount > 0:
                to_pipes[i] = (pipe_len, new_amount)
            elif new_amount == 0:
                to_pipes.pop(i)
            else:
                raise Exception(f"Impossible! Negative new_amount: {new_amount}")
            return
        if new_pipe_len > pipe_len:
            to_pipes.insert(i, (new_pipe_len, 1))
            return

    to_pipes.append((new_pipe_len, 1))

def test(): # generate some tests
    for k in range(2,6):
        for _ in range(20):
            demand = []
            for length in random.sample(range(1, 10), k = k):
                demand.append((length, random.randrange(1,6)))
            demand.sort(reverse=True, key=lambda p: p[0])
            print(f"{demand}")
            res = alg(demand, [(10, inf)])
            print(f"{demand} {res}")
# test()

demand = [(5,20),(4,10),(0.1,1)]
supply = [(6,inf)]
print(alg(demand,supply))

# print(alg([(8, 4), (5, 1), (3, 1), (2, 5), (1, 5)], [(10, inf)])) # a few seconds!
# print(alg([(7, 2), (5, 3), (4, 3), (3, 5), (1, 5)], [(10, inf)])) # a few minutes!!

# print(alg([(50, 3), (10, 2), (1, 1)], [(60, inf)]))
# print(alg([(1,3)], [(6, inf), ((1,3))]))