Description

Xiao H has $n$ bowls to put into a cupboard. She wants to stack them. Each bowl is a right circular frustum (wider at the top and narrower at the bottom). You have measured each bowl’s two radii and height. Please help Xiao H find a stacking order that minimizes the total height of the stack. For example:

Input Format

The first line contains an integer $n$, the number of bowls. Each of the next $n$ lines contains three integers $h$, $r_1$, $r_2$, denoting the bowl’s height and its two radii, where $r_1 < r_2$.

Output Format

Output a single number, the minimal height, rounded to the nearest integer.

3
50 30 80
35 25 70
40 10 90

55

Hint

Constraints: 100% of the testdata satisfies $n \le 9$. The absolute value of every input number does not exceed 1000.

Translated by ChatGPT 5