403856: GYM101341 K Competitions

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Competitionstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Max is preparing hard for the most important event in his life — the ACM ICPC finals. He knows that in the nearest future n programming competitions are going to be held, and that the i-th of them starts at the moment of time ai, ends at the moment of time bi and has usefulness ci. To prepare better, he wants to choose for participating such set of competitions that their total usefulness will be as large as possible, and in case of a tie — that their total duration will be as small as possible. Of course, Max cannot participate in several competitions simultaneously, and also never starts competition after its moment of start and never gives up a competition before its end.

Input

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of competitions.

The next n lines contain three integers each ai, bi, ci separated by a space (0 ≤ ai < bi ≤ 109, 1 ≤ ci ≤ 109) — times of the start and the end of the i-th competition and its usefulness.

Output

In the first line output three integers — the number of competitions k, in which Max should participate, and then their total usefulness and total duration.

In the second line output k integers separated by a space — the numbers of competitions Max should participate in. Competitions are numbered from one in the order they are listed in the input.

If there are several correct answers, output any of them.

ExamplesInput
5
1 6 7
2 3 2
3 8 6
7 10 3
8 9 3
Output
3 11 7
2 3 5
Input
5
1 6 7
2 3 2
3 8 5
7 10 3
8 9 3
Output
2 10 6
1 5

加入题单

上一题 下一题 算法标签: