← 返回题目列表

Codeforces · 864/E

E. 火灾

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

坡旅甲遇到了非常严重的麻烦——他的房子着火了!是时候保存最有价值的物品了。波利卡普估计保存第 i 件物品需要 ti 秒。此外,对于每件物品,他都估算了di的价值——在这一刻之后,该物品i将被完全烧毁,对他来说不再有价值。特别是,如果 ti ≥ di,则第 i 项无法保存。

给定每个项目的值 pi,找到 Polycarp 可以保存的一组项目,使得这些项目的总价值尽可能最大。波利卡普陆续保存了这些物品。例如,如果他先获取物品 a,然后获取物品 b,则物品 a 将在起火后 ta 秒内保存,物品 b 将在起火后 ta + tb 秒内保存。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 波利卡普房子里的物品数量。

以下n行每行包含三个整数ti, di, pi (1 ≤ ti ≤ 20, 1 ≤ di ≤ 2 000, 1 ≤ pi ≤ 20)——保存物品i所需的时间,物品i完全燃烧的时间以及物品i的价值。

输出

在第一行中打印一组已保存项目的最大可能总值。在第二行中打印一个整数 m — 所需集合中的项目数。在第三行中打印 m 个不同的整数——按照 Polycarp 保存它们的顺序保存的项目的编号。项目按照它们在输入中出现的顺序进行 1 索引。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
3 7 4
2 6 5
3 7 6

输出 #1

11
2
2 3

输入 #2

2
5 6 1
3 3 5

输出 #2

1
1
1

注意

在第一个示例中,波利卡普将有时间保存任意两个物品,但为了最大化所保存物品的总价值,他必须保存第二个和第三个物品。例如,他可以先在3秒内保存第三项,然后再在2秒内保存第二项。因此,保存的物品的总价值将为 6 + 5 = 11。

在第二个例子中,Polycarp只能保存第一个项目,因为即使他立即开始保存第二个项目,他也可以在3秒内保存它,但此时该项目已经被完全烧毁。