Portal Hacking Optimization

You are given n portals on a map, numbered from 1 to n. Hacking portal i takes t_i seconds and yields c_i units of resource. However, a portal yields its resource only if it still has energy. In particular, portal i loses all of its energy at time \(d_i\) (i.e. at the beginning of the \(d_i\text{-th}\) second) so that the hacking process must be completed strictly before \(d_i\).

You may hack the portals one after the other (i.e. sequentially starting at time 0). When you choose a set of portals to hack, you are allowed to schedule them in any order. For each hacked portal, if its hacking is completed at time \(f_i\), then it produces resource only if \(f_i < d_i\). Your task is to determine the maximum total resource that can be obtained by selecting a subset of portals and scheduling them feasibly. Additionally, you'll need to output the indices of the portals to hack in increasing order (i.e. sorted in ascending order of their original portal numbers).

Note: If the optimal solution uses a set of portals, then even if the hacking order is different, simply output the portal numbers in ascending order.

Mathematical Formulation:

Let the selected set be S. You need to arrange S in some order such that if \(T\) is the cumulative hacking time before hacking a portal with parameters \(t_i\) and \(d_i\), then the condition
(T + t_i < d_i)
holds for every portal (i \in S). Maximize (\sum_{i \in S} c_i).

</p>

inputFormat

The first line contains a single integer n (the number of portals).

Then n lines follow, each containing three integers: t_i, c_i, and d_i, representing the time required to hack, the resource obtained, and the time when the portal loses energy, respectively.

You may assume that all input values are positive integers.

outputFormat

Output two lines. The first line contains the maximum resource that can be obtained. The second line contains the portal indices (in ascending order) that should be hacked in the optimal solution. The indices should be separated by a single space.

sample

3
1 10 3
2 20 5
1 15 4

45
1 2 3

</p>