#H55. 【拓展题】高效机械
【拓展题】高效机械
Description
你有一些机器人一列排开,间隔 个单位长度,每个机器人最多只能承载 单位重量。
狡猾的合作商趁你不注意,在你的机器人列上放置了 块钢板,第块钢板的起始位置是机器人 ,长度为 ,每 长度的钢板重量为 个单位。
这样下去你的机器人很快因为高负载而停止工作,请你拿走尽可能少的钢板,使得所有机器人都不处于过载的状态。
Format
Input
第一行两个整数 和 ,分别表示钢板的数量和机器人所能承受的最大重量。
接下来 行,第 行有两个整数,,如题目描述所示。
Output
第一行为一个整数 ,表示你在使得所有机器人不过载的情况下,所能拿走的最少钢板数量。
第二行为 个整数,表示你拿走的钢板编号。如果有多种可能的答案,输出 任意一种 即可。
Samples
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9
3
1 4 7
5 1
29 30
30 30
29 29
28 30
30 30
3
1 2 4
6 1
2 3
3 3
2 3
2 2
2 3
2 3
4
1 3 5 6