CF864E.Fire

Polycarp is in really serious trouble — his house is on fire! It's time to save the most valuable items. Polycarp estimated that it would take t__i seconds to save i-th item. In addition, for each item, he estimated the value of d__i — the moment after which the item i will be completely burned and will no longer be valuable for him at all. In particular, if t__i ≥ d__i, then i-th item cannot be saved.

Given the values p__i for each of the items, find a set of items that Polycarp can save such that the total value of this items is maximum possible. Polycarp saves the items one after another. For example, if he takes item a first, and then item b, then the item a will be saved in t__a seconds, and the item b — in t__a + t__b seconds after fire started.

波利卡普遇到了非常严重的问题——他的房子着火了！现在是抢救最宝贵物品的时候了。波利卡普估计，抢救第 $i$ 个物品需要 $t_i$ 秒。此外，他对每个物品还估算了其“损毁时刻” $d_i$——即在该时刻之后，第 $i$ 个物品将被完全烧毁，对他而言将彻底失去价值。特别地，若 $t_i \ge d_i$，则第 $i$ 个物品无法被抢救。

给定每个物品的价值 $p_i$，请找出一个波利卡普能够抢救的物品集合，使得该集合中所有物品的总价值尽可能大。波利卡普按顺序逐个抢救物品。例如，若他先抢救物品 $a$，再抢救物品 $b$，则物品 $a$ 将在火灾开始后 $t_a$ 秒被成功抢救，而物品 $b$ 将在火灾开始后 $t_a + t_b$ 秒被成功抢救。

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of items in Polycarp's house.

Each of the following n lines contains three integers t__i, d__i, p__i (1 ≤ t__i ≤ 20, 1 ≤ d__i ≤ 2 000, 1 ≤ p__i ≤ 20) — the time needed to save the item i, the time after which the item i will burn completely and the value of item i.

第一行包含一个整数 $n$（$1 \leq n \leq 100$）—— 表示 Polycarp 家中物品的数量。

接下来的 $n$ 行中，每行包含三个整数 $t_i,\,d_i,\,p_i$（$1 \leq t_i \leq 20$，$1 \leq d_i \leq 2\,000$，$1 \leq p_i \leq 20$）—— 分别表示拯救第 $i$ 件物品所需的时间、第 $i$ 件物品完全烧毁的时刻，以及第 $i$ 件物品的价值。

In the first line print the maximum possible total value of the set of saved items. In the second line print one integer m — the number of items in the desired set. In the third line print m distinct integers — numbers of the saved items in the order Polycarp saves them. Items are 1-indexed in the same order in which they appear in the input. If there are several answers, print any of them.

第一行输出所保存物品集合的最大可能总价值。
第二行输出一个整数 $m$ —— 所需集合中物品的数量。
第三行输出 $m$ 个互不相同的整数 —— 按 Polycarp 保存它们的顺序给出所保存物品的编号（物品按输入中的顺序从 1 开始编号）。
若存在多个答案，输出任意一个即可。

In the first example Polycarp will have time to save any two items, but in order to maximize the total value of the saved items, he must save the second and the third item. For example, he can firstly save the third item in 3 seconds, and then save the second item in another 2 seconds. Thus, the total value of the saved items will be 6 + 5 = 11.

In the second example Polycarp can save only the first item, since even if he immediately starts saving the second item, he can save it in 3 seconds, but this item will already be completely burned by this time.

在第一个例子中，Polycarp 有时间拯救任意两件物品，但为了使被拯救物品的总价值最大化，他必须拯救第二件和第三件物品。例如，他可以先用 3 秒拯救第三件物品，再用另外 2 秒拯救第二件物品。因此，被拯救物品的总价值为 $6 + 5 = 11$。

在第二个例子中，Polycarp 只能拯救第一件物品，因为即使他立即开始拯救第二件物品，也需要 3 秒才能完成，但此时该物品早已完全烧毁。