MAXN = 10
INF = 1 << 30
def compute_best(item_name, enchantments):
    """
    item_name: name of item
    enchantments: List of (enchantment_name, enchantment_value)
    """
    its = 0

    dp = [[]]
    prev = [[]]
    root = [[]]
    submask_cost = [0]
    # item is first element
    objs = [(item_name, 0)] + enchantments
    for mask in range(1, 1 << len(objs)):
        for i in range(len(objs)):
            if (mask >> i) & 1:
                submask_cost.append(submask_cost[mask^(1<<i)] + objs[i][1])
                break

        if bin(mask).count("1") == 1:
            idx = bin(mask).count("0") - 1
            dp.append([0 for __ in range(MAXN)])
            prev.append([(-1, 0, 0) for __ in range(MAXN)])
            root.append([idx for __ in range(MAXN)])
            continue

        submask = (mask - 1) & mask
        best = [INF for __ in range(MAXN)]
        nprev = [-1 for __ in range(MAXN)]
        nroot = [-1 for __ in range(MAXN)]
        while submask != 0:
            if (mask & 1) == 1 and (submask & 1) == 1:
                submask = (submask - 1) & mask
                # if mask has final item, it must go on left
                continue

            left = dp[mask^submask]
            right = dp[submask]
            for h1, v1 in enumerate(left):
                for h2, v2 in enumerate(right):
                    nh = max(h1,h2)
                    its += 1
                    if nh+1 < MAXN:
                        nv = v1 + v2 + (1<<h1) - 1 + (1<<h2) - 1 + submask_cost[submask]
                        if nv < best[nh+1]:
                            best[nh+1] = nv
                            nprev[nh+1] = (submask, h1, h2)
                            nroot[nh+1] = root[mask^submask][h1]
            submask = (submask - 1) & mask

        dp.append(best)
        prev.append(nprev)
        root.append(nroot)

    bestvalue = min(dp[-1])

    besth = -1
    for i in range(MAXN):
        if dp[-1][i] == bestvalue:
            besth = i
            break

    def format(mask, rt):
        other = []
        for i in range(len(objs)):
            if ((mask>>i)&1) == 1 and i != rt:
                other.append(objs[i][0])
        other_str = "" if not other else f" (w/ {' + '.join(other)})"
        return f"{objs[rt][0]}{other_str}"

    instructions = []
    stack = [((1 << len(objs)) - 1, besth)]
    while len(stack) > 0:
        submask, curh = stack.pop()
        if bin(submask).count("1") == 1:
            continue
        rightmask, lefth, righth = prev[submask][curh]
        leftmask = submask^rightmask
        instructions.append(f"Combine {format(leftmask, root[leftmask][lefth])} with {format(rightmask, root[rightmask][righth])}")
        stack.append((leftmask, lefth))
        stack.append((rightmask, righth))

    print(its)
    return instructions[::-1]

print("\n".join(compute_best("Boots", [
    ("Soul Speed III", 12),
    ("Thorns III", 12),
    ("Depth Strider III", 6),
    ("Feather Falling IV", 4),
    ("Protection IV", 4),
    ("Unbreaking III", 3),
    ("Mending", 2),
])))

"""
Output:
Combine Boots with Soul Speed III
Combine Thorns III with Feather Falling IV
Combine Boots (w/ Soul Speed III) with Thorns III (w/ Feather Falling IV)
Combine Depth Strider III with Unbreaking III
Combine Boots (w/ Soul Speed III + Thorns III + Feather Falling IV) with Depth Strider III (w/ Unbreaking III)
Combine Protection IV with Mending
Combine Boots (w/ Soul Speed III + Thorns III + Depth Strider III + Feather Falling IV + Unbreaking III) with Protection IV (w/ Mending)
"""