Problem I
Tours de Sales Force

The Weight For It company sells home gym equipment to clients in multiple states. Each salesperson in a state is currently in charge of a specific district made up of $3$-$8$ clients. Each salesperson has mapped out the shortest path with which to visit all of their clients in one day and ending up back where they started (this is known as their sales tour).

Sales have gotten a little light for Weight For It so they’ve decided to cut their sales force in half, reassigning each of the districts of the fired half of the workforce in one state to one in the un-fired half. In order to be fair, each of the un-fired sales persons are assigned exactly one of these districts. After the assignments the remaining salespeople will have to recalculate their minimum sales tours, and as a further cost cutting measure Weight For It would like to assign the districts so that the overall length of all these new sales tours is as small as possible.

For example, Figure 1 on the left shows the configuration of four districts in one state. Suppose that the salespeople for districts $A$ and $B$ are fired. Then the best reassignment for those districts would be to assign the six clients from district $A$ to the salesperson for district $C$ and the four clients from district $B$ to the salesperson for district $D$. The resulting shortest sales tours for each of the new districts $C^{\prime }$ and $D^{\prime }$ are shown on the right.

Figure 1: (a) Four districts before firings. (b) Two districts after firings. This example corresponds to Sample Input $1$.

Input

Input starts with a positive even integer $d$ ($d \leq 50$) indicating the number of districts. Each of the next $d$ lines lists the number and locations of the clients in each of the districts, one district per line starting with district one. Each of these lines starts with an integer $n$ ($3 \leq n \leq 8$) indicating the number of clients in the district, followed by $n$ integer coordinate pairs $x$ $y$ ($-10\, 000 \leq x, y \leq 10\, 000$) indicating the locations of the clients. The first $d/2$ districts listed are those of the fired salespersons. The distance between any two clients is the Euclidean distance and all client locations are distinct.

Output

Display the sum of all the sales tours prior to the firings followed by the sum of all the sales tours after the firings. Your answers should be correct to within an absolute error of $10^{-2}$.

4
6 0 10 0 20 5 30 10 20 10 10 5 0
4 40 20 40 30 50 20 50 30
4 20 10 30 20 20 20 30 10
3 55 10 45 10 50 0

177.082039 179.442719