Minimizing the Stacked Height of Nested Bowls

Little H has n bowls that she wants to place in a cabinet by stacking them. Each bowl is shaped as a right circular truncated cone (i.e. its top is wider than its bottom). For each bowl, you are given its bottom radius r, its top radius R (with r < R), and its height h.

The bowls are to be stacked in such a way that one bowl is nested inside the previous one if possible. When a bowl j is placed on top of bowl i, it can sink into bowl i until the outer wall of bowl j touches the inner wall of bowl i. The inner wall of bowl i is linear: at a vertical distance x from its top edge (0 ≤ x ≤ h_i), the available radius is $$R_i - \frac{R_i - r_i}{h_i}x.$$ Similarly, the outer wall of bowl j (measured from its top edge downward) is given by $$R_j - \frac{R_j - r_j}{h_j}x.$$ Assume that the two bowls can be nested (i.e. bowl i can hold bowl j) only if both of the following conditions hold:

• The top radius of bowl i is larger than that of bowl j: \(R_i > R_j\).
• The slope of bowl i is steeper than the slope of bowl j, i.e. \(\frac{R_i - r_i}{h_i} > \frac{R_j - r_j}{h_j}\).

If these conditions hold, then the bowl j will make contact with bowl i when lowered by a distance $$x = \frac{R_i - R_j}{\frac{R_i - r_i}{h_i} - \frac{R_j - r_j}{h_j}},$$ and the effective overlap is \(\min(h_j, x)\). Otherwise, no nesting occurs, and bowl j adds its full height when placed on top of bowl i.

If bowl j is placed on bowl i, its additional contribution to the total stack height is $$\max\Big\{0,\, h_j - \min\Big(h_j,\; \frac{R_i - R_j}{\frac{R_i - r_i}{h_i} - \frac{R_j - r_j}{h_j}}\Big)\Big\}.$$ The bottom bowl contributes its full height. Arrange all bowls in some order (a permutation) so that the total stack height is minimized.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) (the number of bowls). Each of the following \(n\) lines contains three positive numbers r, R and h, representing the bottom radius, the top radius, and the height of a bowl, respectively.

You can assume that \(r < R\) for every bowl.

outputFormat

Output the minimum total height of the stacked bowls. Print the result as a floating point number with at least 6 digits after the decimal point.

sample

2
1 3 2
1 2 1

3.000000