"""Original weighted half-open interval DP, independent subset oracle."""
from itertools import combinations,permutations
import json
def validate(jobs):
 if type(jobs) is not list or len(jobs)>8:raise ValueError('at most8 jobs')
 ids=[]
 for j in jobs:
  if type(j) is not dict or set(j)!=set(['id','start','end','value']) or type(j['id']) is not str or not j['id']:raise ValueError('exact bounded record')
  if any(type(j[k]) is not int or abs(j[k])>100 for k in ['start','end','value']) or j['start']>=j['end'] or j['value']<0:raise ValueError('positive length, nonnegative bounded integer value')
  ids.append(j['id'])
 if len(set(ids))!=len(ids):raise ValueError('unique ids')
def solve(jobs):
 validate(jobs);s=sorted(jobs,key=lambda x:(x['end'],x['start'],x['id']));dp=[0];p=[];steps=[]
 for q,j in enumerate(s):
  prev=max([i+1 for i in range(q) if s[i]['end']<=j['start']]+[0]);p.append(prev)
  inc=j['value']+dp[prev];exc=dp[q];dp.append(max(inc,exc));steps.append({'job':j['id'],'p_dp_index':prev,'include':inc,'exclude':exc,'best':dp[-1]})
 chosen=[];q=len(s)
 while q:
  if s[q-1]['value']+dp[p[q-1]]>dp[q-1]:chosen.append(s[q-1]['id']);q=p[q-1]
  else:q-=1
 return {'sorted_jobs':s,'trace':steps,'dp':dp,'value':dp[-1],'chosen_ids':list(reversed(chosen)),'tie_policy':'exclude current sorted job'}
def subsets(jobs):
 rows=[]
 for m in range(1<<len(jobs)):
  chosen=[j for i,j in enumerate(jobs) if m&(1<<i)];ok=all(a['end']<=b['start'] or b['end']<=a['start'] for a,b in combinations(chosen,2))
  rows.append({'ids':[j['id'] for j in chosen],'compatible':ok,'value':sum(j['value'] for j in chosen)})
 return rows
def demo():
 jobs=[dict(id='A',start=0,end=3,value=5),dict(id='B',start=3,end=5,value=5),dict(id='C',start=0,end=5,value=11)]
 out=solve(jobs);oracle=subsets(jobs);assert out['value']==max(r['value'] for r in oracle if r['compatible'])==11
 greedy=[];last=-10**6
 for j in sorted(jobs,key=lambda j:(j['end'],j['start'],j['id'])):
  if j['start']>=last:greedy.append(j);last=j['end']
 assert sum(j['value'] for j in greedy)==10
 cases=[[],jobs[:2],[dict(id='X',start=1,end=2,value=0)],[dict(id='X',start=0,end=1,value=2),dict(id='Y',start=0,end=1,value=2)],jobs+[dict(id='D',start=5,end=7,value=3),dict(id='E',start=1,end=6,value=20)]]
 tested=[]
 for c in cases:
  result=solve(c);ref=subsets(c);assert result['value']==max(x['value'] for x in ref if x['compatible'])
  witness=[j for j in c if j['id'] in result['chosen_ids']]
  assert len(witness)==len(result['chosen_ids']) and sum(j['value'] for j in witness)==result['value']
  assert all(a['end']<=b['start'] or b['end']<=a['start'] for a,b in combinations(witness,2))
  tested.append({'jobs':c,'result':result,'subset_count':len(ref),'witness_unique_compatible_value_equal':True})
 for p in permutations(jobs):assert solve(list(p))==out
 rejected=[]
 for bad in [[dict(id='X',start=0,end=0,value=1)],[dict(id='X',start=2,end=1,value=1)],[jobs[0],jobs[0]],[dict(id='X',start=0,end=1,value=-1)]]:
  try:solve(bad)
  except ValueError:rejected.append(bad)
  else:raise AssertionError('expected rejection')
 return {'jobs':jobs,'solution':out,'all_eight_subsets':oracle,'earliest_finish_greedy':{'ids':[j['id'] for j in greedy],'value':10},'boundary_rule':'[start,end), touching is compatible','additional_cases':tested,'six_input_permutations_same_result':True,'rejected':rejected,'real_calendar_or_scheduler':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))