坡旅甲遇到了非常严重的麻烦——他的房子着火了!是时候保存最有价值的物品了。波利卡普估计保存第 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秒内保存它,但此时该项目已经被完全烧毁。