Background

JYY has just returned from a trip to Russia and bought a lot of beautiful nesting dolls as souvenirs. Because JYY was too excited, he opened all of the nesting dolls. Since many of the dolls look very similar, JYY now does not know how to put them back (he really cannot figure out which doll should be put into which).

Problem 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