Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Bowlstack
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 889Accepted: 351

Description

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 disregarded.

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.

Input

On the first line of the input is a positive integer, telling the number of test cases to follow. Each case starts with one line containing an integer n, the number of bowls (2 ≤ n ≤ 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.

Output

For each test case, output one line containing the minimal stack height, truncated to an integer (note: truncated, not rounded).

Sample Input

2
2
60 20 30
40 10 50
3
50 30 80
35 25 70
40 10 90

Sample Output

70
55

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator