ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1815. Farm in San Andreas

Time limit: 0.5 second
Memory limit: 64 MB
Government of the cities Los Santos, San Fierro and Las Venturas, situated within the state San Andreas, decided to build a farm. Citizens of Los Santos claimed that they will travel to the farm by subway, citizens of San Fierro will travel by car and citizens of Las Venturas will travel by train.
You know the amount of money required to build one kilometer of subway line, one kilometer of highway and one kilometer of railroad. Help the government choose a place for the farm that would minimize the total amount of money required to build roads of all three types.

Input

The first line contains the number of test cases t (1 ≤ t ≤ 104). Each test case consists of four lines. The first three lines contain the coordinates of Los Santos, San Fierro and Las Venturas, respectively. All coordinates are integers and don't exceed 1000 in their absolute value. The fourth line contains the costs of building a kilometer of subway line, highway and railroad. These costs are positive integers, not exceeding 1000.

Output

For each test case output in a single line the minimal amount of money required to build all roads from the cities to the farm, with absolute or relative error not exceeding 10−9.

Sample

inputoutput
2
0 0
1 0
0 1
1 1 1
-3 0
3 5
0 -1
7 9 8
1.9318516526
81.1600672826
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010