def main1(n,m,a,lrp): g=[[] for _ in range(n+1)] for l,r,p in lrp: # 区間[l,r]を作る→次作れるのは[r+1,x] g[l-1].append([r,p]) inf=float('inf') seen=[-inf]*n*2 # seen[0*n+v]:現在vにいて、左に黒線ありのときの最大値 # seen[1*n+v]:現在vにいて、左に黒線なしのときの最大値 seen[0]=0 ans=0 for v in range(n): if seen[v]!=-inf: if v+1==n: ans=max(ans,seen[v]) elif seen[n+v+1]