Russian Dolls

A Russian doll is a wooden souvenir where a smaller doll sits inside a bigger one. Take the whole set apart and look at the dolls one by one. Doll $i$ has an outer volume $out_i$, the volume it occupies in space, and an inner volume $in_i$, the volume of the empty space inside it. You may put one doll inside another when the outer volume of the first doll is strictly less than the inner volume of the second one. Two dolls that go inside the same doll cannot lie side by side, so they must be nested one inside the other.

Every doll charges for the empty space left in it. You pay $cost_i$ for each unit of empty space that belongs directly to doll $i$, that is, the part of its inner space that the doll placed directly inside it does not occupy. A doll with nothing inside it has all of $in_i$ empty. You may arrange the dolls any way the rules allow, and you do not have to nest all of them. Find the smallest total cost you have to pay.

The first line contains an integer $N$ ($1 \le N \le 1000$), the number of dolls. The $i$-th of the next $N$ lines contains three integers $out_i$, $in_i$, $cost_i$ ($1 \le in_i < out_i \le 1000$, $1 \le cost_i \le 1000$), the outer volume, the inner volume, and the cost of one unit of empty space of doll $i$.

Print one integer $P$, the minimum cost you have to pay.