Baking bread is my favourite spare-time pursuit. I have a
number of stainless steel mixing bowls with straight sides, a
circular bottom and a wider circular top opening.
Geometrically, my bowls are truncated circular cones and for
this problem, the thickness of the metal may be
I store these bowls stacked in the natural way, that is with
a common vertical axis, and I stack them in an order that
minimises the total height of the stack. Finding this minimum
is the purpose of your program.
Figure 1: Illustrations of the two sample cases
On the first line of the input is a positive integer,
telling the number of test cases to follow (at most
$10$). Each case starts
with one line containing an integer $n$, the number of bowls ($2\leq n \leq 9$). The following
$n$ lines each contain
three positive integers $h, r,
R$, specifying the height, the bottom radius and the top
radius of the bowl, and $r<R$ holds true. You may also
assume that $h,r,R<1000$.
For each test case, output one line containing the minimal
stack height, truncated to an integer (note:
truncated, not rounded).
|Sample Input 1
||Sample Output 1
60 20 30
40 10 50
50 30 80
35 25 70
40 10 90