Hide

Problem D
Wood Cutting

Yraglac recently decided to get into the wood cutting business, and now has $N$ customers who would like to have their wood cut. A piece of wood of size $s$ takes $s$ time units to cut, and Yraglac can only cut a single piece of wood at a time. To maximize customer happiness, Yraglac would like to minimize the average total time a customer has to wait to have all of their wood pieces cut. Can you help him?

Input

The first line contains a single integer $T \leq 10$ giving the number of test cases. Each test case begins with an integer $N$ ($1\leq N \leq 10^5$), the number of customers. $N$ lines follow, where the $i$th line begins with an integer $W_ i$ ($1 \leq W_ i \leq 10^5$), the number of wood pieces that customer $i$ would like to have cut, followed by $W_ i$ integers, the sizes of the wood pieces of the customer. Each wood piece has a size between $1$ and $1\, 000$ inclusive. The total number of wood pieces will not exceed $10^5$.

Output

For each test case, output a single line containing the minimum average total time a customer will wait to have all of their wood pieces cut. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.

Sample Input 1 Sample Output 1
2
1
2 7 5
2
1 7
1 5
12.0000000000
8.5000000000

Please log in to submit a solution to this problem

Log in