Doll Nesting Minimization

You are given N nesting dolls numbered from $1$ to $N$. Each doll i has an outer diameter \(Out_i\) and an inner diameter \(In_i\) with \(In_i < Out_i\). One doll i can be placed inside another doll j if and only if \(Out_i < In_j\). However, each doll can hold at most one directly nested doll. In other words, if doll i is placed inside doll j, then no other doll can be put directly inside doll j even if it satisfies \(Out_k < In_j\). Nevertheless, if doll k satisfies \(Out_k < In_i\), it is allowed to nest doll k inside doll i (and then the combined doll can be nested inside doll j).

Each doll i also has a beauty rating \(B_i\). The internal gap (or empty space) of a doll depends on whether it holds another doll. If doll j is empty its gap is \(In_j\). If doll j directly contains doll i, then its gap becomes \(In_j - Out_i\). The dissatisfaction for doll j is computed as:

[ \text{dissatisfaction}_j = \begin{cases} (In_j - Out_i)\times B_j, & \text{if doll } j \text{ contains doll } i,\ In_j \times B_j, & \text{if doll } j \text{ is empty.} \end{cases} ]

The overall dissatisfaction is the sum of the individual dissatisfactions for all dolls. Your task is to find a valid nesting arrangement that minimizes the total dissatisfaction.

Hint: Notice that if doll j remains empty its dissatisfaction is \(In_j \times B_j\). If doll j contains doll i, the dissatisfaction reduces by \(B_j \times Out_i\) compared to being empty. Thus, if we define the saving of nesting doll i inside doll j as

[ S_{j,i} = B_j \times Out_i, ]

then the total dissatisfaction can be written as

[ \text{Total Dissatisfaction} = \sum_{j=1}^{N} (In_j \times B_j) - \sum_{(j,i) \in M} (B_j \times Out_i), ]

where \(M\) is a set of valid (non–conflicting) nesting pairs. In a valid nesting arrangement, a doll can act as an inner doll in at most one pair and as a container doll in at most one pair (although a doll may appear in both roles in a chain nesting). Thus, the problem reduces to choosing a set of pairs (i, j) with \(Out_i < In_j\) (and implicitly \(Out_i < Out_j\)) so that the sum of savings is maximized. Finally, print the minimized total dissatisfaction.

inputFormat

The first line contains an integer N indicating the number of dolls.

Then follow N lines, each containing three integers: Out_i, In_i, and B_i (for \(1 \le i \le N\)), representing the outer diameter, inner diameter, and beauty rating of doll i, respectively. It is guaranteed that \(In_i < Out_i\) for all dolls.

outputFormat

Output a single integer: the minimized total dissatisfaction achievable by a valid nesting scheme.

sample

2
1 2 1
3 4 2

8