/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 1000 点
問題文
TMJN君はアニメが大好きです。
昨晩は、N 本のアニメを見る予定でした。アニメには 1 から N の番号が付けられており、i 番目のアニメの放映開始時刻は A_i、終了時刻は B_i です。
しかし、昨晩は疲れていたため、気が付いたら朝に！
そう、アニメを見ずに寝てしまったのです。
しかしご安心を、このTMJN君、時間遡行ができるのです！
そこで、時間遡行をして全てのアニメを鑑賞することにしました。しかし、時間遡行は体力の消耗が激しいので、なるべく遡る時間は短くしたいです。
さて、TMJN君が目覚めた現在時刻は T です。
TMJN君は瞬時にテレビのチャンネルを変えることができますが、同時に複数のアニメを鑑賞することはできません。
また、あるアニメの視聴を開始したら、そのアニメを最後まで鑑賞します。あるアニメの鑑賞中に他のアニメを見るためにチャンネルを切り替えることは絶対に行いません。
そのとき、TMJN君が遡る時間の合計の最小値と、それを達成するためのアニメを視聴する順番を出力してください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^9
- 0 \leq A_i < B_i \leq T
小課題
この課題には 3 つの小課題があります。- (250 点) A_i \leq A_j < B_i である (i, j) (i ≠ j) の組が存在しない。すなわち 2 つのアニメが同時に放映されることはない。
- (250 点) A_1 = 0, B_1 = T を満たす。
- (500 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N T
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
A_N B_N
出力
N+1 行に渡って出力して下さい。
1 行目には遡る時間の合計の最小値を出力してください。
i+1 (1 \leq i \leq N) 行目には i 番目に視聴するアニメの番号を出力してください。
遡る時間の合計が最小となる答えが複数ある場合は、どれを出力しても構いません。
入力例1
3 141 5 9 26 53 58 97
出力例1
136 1 2 3
アニメ 1、アニメ 2、アニメ 3 の順に視聴した時、遡る時間の合計は 136 となります。
これより遡る時間の合計が短くなる視聴順は存在しません。
なお、この入力例は小課題 1 の制約を満たします。
入力例2
5 10 0 10 2 5 6 9 1 8 5 7
出力例2
25 2 5 3 4 1
例えば、アニメ 2、アニメ 5、アニメ 3、アニメ 4、アニメ 1 の順に視聴した時、遡る時間の合計は 25 となります。
これより遡る時間の合計が短くなる視聴順は存在しません。
なお、この入力例は小課題 2 の条件を満たします。
入力例3
7 30 1 15 23 25 13 21 0 5 18 20 4 11 19 22
出力例3
47 6 4 1 3 5 7 2
writer: TMJN