tv-channel

Recently scientists discovered new field to research. They explore how to organize TV schedule to maximize happiness of viewers. They proved that a change of happiness after viewing a TV-show depends only on this show and the previous show.

Formally, each TV-show is characterized by three values: 
ti, ai and bi , where ti is the type of the i-th TV-show, ai and bi are how happiness changes after viewing the i-th show. If the previous TV-show exists
(i.e. the current show is not the first) and the previous show type equals to the type of the current show then happiness is increased by ai. Otherwise after viewing the i-th TV-show happiness is increased by bi.

There are n TV-shows in total numbered from 1 to n. The problem is to choose some TV-shows and order them in a sequence in a way to maximize happiness after viewing all of them one after another. Actually some TV-shows do not increase happiness, if quality of a TV-show is very low it can have negative a
and/or b values. It is possible to choose empty set of TV-shows, in that case happiness will no be changed. Each show can be used at most once.

Input
The first line contains integer n (1 ≤ n ≤ 600)  the number of TV-shows. Each of the following n lines describes one show. The i-th line contains three integers: ti, ai , bi (1 ≤ ti ≤ n; |ai|, |bi| ≤ 105)  the typ eand the values of the i-th show.

Output
The output should contain two lines. Output two integer numbers c and k in the first line, where c maximal happiness change after viewing subset of shows in an appropriate order, k (0 ≤ k ≤ n)  the number of shows in the optimal subset. Output the sequence of TV-shows in the order that maximizes
happiness in the second line. Formally, output k indices f1, f2, . . . , fk (1 ≤ fj ≤ n), where f1 is the first show to be shown, f2 is the second show to be shown, and so on. If there are many optimal solutions, any is acceptable

SAMPLE INPUT
4
1 10 5
1 5 10
2 -1 -1
3 5 1

SAMPLE OUTPUT
21 3
4 2 1

Source: hackerearth | Difficulty: EASY


Solutions: