AT_tkppc4_2_k 時をかけるTMJN

[problemUrl]: https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_k TMJN君はアニメが大好きです。 昨晩は、$ N $ 本のアニメを見る予定でした。アニメには $ 1 $ から $ N $ の番号が付けられており、$ i $ 番目のアニメの放映開始時刻は $ A_i $、終了時刻は $ B_i $ です。 しかし、昨晩は疲れていたため、気が付いたら朝に！ そう、アニメを見ずに寝てしまったのです。 しかしご安心を、このTMJN君、時間遡行ができるのです！ そこで、時間遡行をして全てのアニメを鑑賞することにしました。しかし、時間遡行は体力の消耗が激しいので、なるべく遡る時間は短くしたいです。 さて、TMJN君が目覚めた現在時刻は $ T $ です。 TMJN君は瞬時にテレビのチャンネルを変えることができますが、同時に複数のアニメを鑑賞することはできません。 また、あるアニメの視聴を開始したら、そのアニメを最後まで鑑賞します。あるアニメの鑑賞中に他のアニメを見るためにチャンネルを切り替えることは絶対に行いません。 そのとき、TMJN君が遡る時間の合計の最小値と、それを達成するためのアニメを視聴する順番を出力してください。

入力は以下の形式で標準入力から与えられます。 > $ 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\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ T\ \leq\ 10^9 $ - **$ 0\ \leq\ A_i $** ### 小課題 この課題には $ 3 $ つの小課題があります。 1. (250 点) $ A_i\ \leq\ A_j\ である\ (i,\ j) $ $ (i\ ≠\ j) $ の組が存在しない。すなわち $ 2 $ つのアニメが同時に放映されることはない。 2. (250 点) $ A_1\ =\ 0,\ B_1\ =\ T $ を満たす。 3. (500 点) 追加の制約はない。 ### Sample Explanation 1 アニメ $ 1 $、アニメ $ 2 $、アニメ $ 3 $ の順に視聴した時、遡る時間の合計は $ 136 $ となります。 これより遡る時間の合計が短くなる視聴順は存在しません。 なお、この入力例は小課題 $ 1 $ の制約を満たします。 ### Sample Explanation 2 例えば、アニメ $ 2 $、アニメ $ 5 $、アニメ $ 3 $、アニメ $ 4 $、アニメ $ 1 $ の順に視聴した時、遡る時間の合計は $ 25 $ となります。 これより遡る時間の合計が短くなる視聴順は存在しません。 なお、この入力例は小課題 $ 2 $ の条件を満たします。