Description

JYY has a total of $N$ disassembled nesting dolls, numbered from $1$ to $N$. Doll $i$ has an outer diameter $Out_i$ and an inner diameter $In_i$ ($In_i<Out_i$).

For dolls $i$ and $j$, if $Out_i<In_j$, then doll $i$ can be put inside doll $j$.

Note that inside a single doll, it is not allowed to place multiple dolls side by side.

That is, if we put $i$ inside $j$, and there is another doll $k$ that also satisfies $Out_k<In_j$, then we are not allowed to put $k$ inside $j$ at this time (because $j$ already contains $i$). However, if $k$ also satisfies $Out_k<In_i$, then we are allowed to first put $k$ inside $i$, and then put $k$ and $i$ together as a whole into $j$.

JYY believes that a good set of nesting dolls should have as little empty space inside as possible. If doll $j$ contains doll $i$, then we define the empty space produced inside doll $j$ as $In_j-Out_i$. If doll $j$ contains nothing, then the empty space of doll $j$ is $In_j$.

JYY also hopes that the better-looking dolls should be filled as much as possible; for the less good-looking ones, he cares relatively less. Therefore, JYY assigns each doll $i$ a beauty value $B_i$. If this doll still has $K$ empty space inside, then JYY will have a dissatisfaction of $K\times B_i$ for this doll.

The dissatisfaction of a nesting plan is the sum of the dissatisfaction produced by each doll. JYY wants to find a nesting plan with the minimum total dissatisfaction.

Input Format

The first line contains a positive integer $N$. The next $N$ lines each contain three positive integers $Out_i,In_i,B_i$, representing the outer diameter, inner diameter, and beauty value of doll $i$.

Output Format

Output one integer in a single line, representing the minimum possible dissatisfaction.

3
5 4 1
4 2 2
3 2 1

7

Hint

For $100\%$ of the testdata, $N\leq 2\times 10^5$, $1\leq In_i<Out_i\leq 10^4$, $1\leq B_i\leq 10^9$.

Translated by ChatGPT 5