← 返回题目列表

AtCoder · tkppc4_2_k

K. TMJN 花时间

中文机器翻译题面 查看原题

配点: 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 有两个子作业。
  1. (250 点) A_i \leq A_j < B_i 是 (i, j) (i ≠ j) 的组合不存在。也就是说 2 多部动画不会同时播放。
  2. (250 点) A_1 = 0, B_1 = T 很满意。
  3. (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