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 $T10$ giving the number of test cases.

Each test case begins with an integer $N(1N{10}^5),$ the number of

customers. $N$ lines follow, where the $i$ th line begins with an integer $W_i($

$1W_i{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 $1000$ 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$

$2$

$1$

$275$

$2$

$17$

$15$

Sample Output $1$

$12\mathrm{.}0000000000$

$8\mathrm{.}5000000000$

$($a$)$ Implement a greedy algorithm using your preferred language and submit your implementation via Kattis. Submit a screenshot of your submission that clearly shows your code.

$($b$)$ Prove that your algorithm is correct by proving the greedy choice and optimal substructure properties.