配点: 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
作者: TMJN