At the Interregional Robot Programming Olympiad, competitions are held in one round and in an unusual format. The tasks are given to the participants sequentially, not all at the very beginning of the round, and each i-th task (1 ≤ i ≤ n) becomes available to the participants at its time s
i. Upon receipt of the next task, each participant must immediately determine whether he will solve it or not. If he chooses to solve this problem, then he has t
i minutes to submit its solution for verification, and during this time he cannot switch to solving another problem. If the participant refuses to solve this problem, then in the future he cannot return to it. At the moment when the time allotted for the task that the participant is solving has ended, he can start solving another task that became available at the same moment, if there is such a task, or wait for another task to appear. At the same time, for the correct solution of the i-th problem, the participant receives c
i points.
Artur, who represents one of the regional artificial intelligence centers at the interregional Olympiad, understands that not only the ability to solve problems, but also the correct strategic calculation of which problems need to be solved and which ones to skip, plays an important role at such an Olympiad. He, like all participants, before the start of the tour knows at what point in time each task will become available, how much time will be allotted for its solution and how many points you can get for solving it. Artur is a talented student and therefore will be able to successfully solve any problem he chooses to solve at the Olympiad in the allotted time and pass for verification.
It is required to write a program that determines the maximum number of points Arthur can get with the optimal choice of problems that he will solve, as well as the number and list of such problems.
Input
The first line contains one integer n (1 ≤ n ≤ 10
5) the number of problems in the Olympiad.
The next n lines contain descriptions of the problems, three numbers on each line: si the moment the i-th problem appears in minutes, t
i the time allotted for its solution in minutes, and ci how many points the participant will receive for solving this problem (1 ≤ s
i, t
i, c
i ≤ 10
9).
Imprint
First line must contain a single number – the maximum number of points that Arthur can get at the Olympiad.
The second line should contain one integer m - the number of tasks to be solved with the optimal choice.
The third line should contain m space-separated integers - the numbers of these problems in the order in which they were solved. The tasks are numbered, starting from one, in the order they are described in the input file.
If there are several optimal answers, print any of them.
Examples
| # |
Input |
Output |
| 1 |
2
1 1 1
2 2 2
| 3
2
1 2
|
| 2 |
3
1 2 1
3 2 1
2 4 3
| 3
1
3 |