AT_tkppc4_2_k.時をかけるTMJN

TMJN 君非常喜欢看动漫。昨晚，他原计划要观看 $N$ 部动漫。这些动漫被编号为 $1$ 到 $N$，其中第 $i$ 部动漫的播放开始时间是 $A_i$，结束时间是 $B_i$。然而，由于太累，他一觉睡到了早上，错过了所有的动漫。不过，别担心，TMJN 君有时间回溯的能力！因此，他决定利用这项能力来补看这些动漫。不过，时间回溯会耗费大量体力，因此他希望尽量减少所需的回溯时间。

TMJN 君醒来的时间是 $T$。他可以瞬间切换电视频道，但不能同时观看多部动漫。并且，一旦开始观看某部动漫，就必须从头看到尾，不能中途切换去看其他动漫。

请你计算出 TMJN 君需要的最小回溯时间，以及实现该目标的动漫观看顺序。

输入将以如下格式提供：

$N$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ ... $A_{N-1}$ $B_{N-1}$ $A_N$ $B_N$

输出分为 $N+1$ 行：

• 第 1 行输出需要回溯的总时间的最小值。
• 接下来的 $N$ 行，每行输出按照制定顺序观看的动漫编号。

如果有多种观看顺序都能达到最小回溯时间中的任意一种。

约束条件

• 所有输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq T \leq 10^9$
• $0 \leq A_i$

子任务

题目包含 $3$ 个子任务：

1. （250 分）对于所有 $i, j$（$i \neq j$），不存在 $A_i \leq A_j$ 的情况，表示任意两部动漫不会同时播放。
2. （250 分）满足 $A_1 = 0, B_1 = T$。
3. （500 分）无附加约束。

示例解释 1

按照动漫 $1$、动漫 $2$、动漫 $3$ 的顺序观看时，所需回溯的总时间为 $136$。没有比这个更短的回溯时间了。注意，此输入示例满足子任务 $1$ 的条件。

示例解释 2

例如，按照动漫 $2$、动漫 $5$、动漫 $3$、动漫 $4$、动漫 $1$ 的顺序观看时，所需回溯的总时间为 $25$。没有比这个更短的回溯时间了。注意，此输入示例满足子任务 $2$ 的条件。

本翻译由 AI 自动生成