You own a large island where you want to build an industry of your own. But the water around the island is not very deep so you can only use small boats to carry goods, but over the years this has proven to be a very slow process and also a risky one. So now you have bought a large Cargo Plane which can land anywhere on the island. Your job is to find an optimal place for landing. Let us denote is optimal place as L. Some additional information to solve this problem are: • You already have three warehouses in the island to store goods. • You know the how many goods can be kept in each warehouse and the amount of goods in the cargo plane. These are denoted by four positive integers. • From the landing location L you plan to use three different trucks to carry cargo to the three warehouses. Each truck will start from L and reach the desired warehouse using the straight-line route, and a truck will not unload in more than one warehouse under any circumstances. After unloading, a truck will return to L using the same route. • Multiple trips can be used to take all the goods to the warehouses. But after delivering all goods to the warehouses the three trucks will finally return to L. • If the total amount of goods you can keep in the three warehouses is greater than goods bought via plane, you can decide what amount to be put in which warehouse. • The capacity of all three trucks is 1. So each of the truck can take one unit of goods in each trip. Given the location of the three warehouses, their capacity and the amount of goods bought by the Cargo Plane, your job is to find such a location for landing so that the total distance covered by three trucks is minimum. You can assume that when the plane arrives all three warehouses are empty. You don’t have to print the location of the landing location but only need to print the minimum total distance covered by the three trucks. Note that you have been asked to minimize the total distance covered by three trucks and need not to minimize the total time needed to carry the goods to the warehouses. Input First line of the input file contains a positive integer N (N ≤ 20, 000) which denotes the number of test cases. The input for each test case is given in two lines and the description of these two lines is given below: First line of each test contains six integers Ax, Ay, Bx, By, Cx and Cy (0 ≤ Ax, Ay, Bx, By, Cx, Cy ≤ 1, 000), these integers denote that (Ax, Ay), (Bx, By) and (Cx, Cy) are the locations of three warehouses A, B and C respectively in Cartesian coordinate system. You can assume that these points are not collinear. ThesecondlinecontainsfourintegersCA,CB,CC andWP (20≤2CA,2CB,2CC,WP ≤2,000 and WP ≤ CA + CB + CC ) which denotes the capacity of the three warehouses A, B, C and the amount of goods bought by the plane respectively.
2/2 Output For each set of input produce one line of output. This line contains a floating point number which denotes total distance covered by the three trucks when the cargo plane lands at an optimal location. This number should have four digits after the decimal point. An optimal location is the location from which the cost (sum of total distance covered by the three trucks) of carrying the goods to the warehouses is minimum. Sample Input 1 10 10 100 10 50 80 10 10 10 30 Sample Output Case 1: 2960.5351