Weight For It 公司向多个州的客户销售家庭健身器材。目前，每个州的每位销售人员负责一个由 3 到 8 名客户组成的特定区域。每位销售人员都规划了一条最短路径，以便在一天内拜访其所有客户（这被称为他们的销售巡回路线）。

由于 Weight For It 公司的销售额有所下降，他们决定裁减一半的销售人员，并将被裁减的一半销售人员所负责的区域重新分配给未被裁减的另一半销售人员。为了公平起见，每位未被裁减的销售人员恰好被分配到一个这样的区域。在完成分配后，剩余的销售人员必须重新计算他们的最短销售巡回路线。作为进一步的成本削减措施，Weight For It 公司希望通过分配区域，使得所有这些新的销售巡回路线的总长度尽可能小。

例如，图 I.1 左侧展示了一个州内四个区域的配置。假设负责区域 $A$ 和 $B$ 的销售人员被裁减。那么，这些区域的最佳重新分配方案是将区域 $A$ 的 6 名客户分配给负责区域 $C$ 的销售人员，并将区域 $B$ 的 4 名客户分配给负责区域 $D$ 的销售人员。右侧展示了新的区域 $C'$ 和 $D'$ 的最短销售巡回路线。

图 I.1：(a) 裁员前的四个区域。(b) 裁员后的两个区域。此示例对应于样例输入 1。

输入格式

输入以一个正偶数 $d$ ($d \le 50$) 开头，表示区域的数量。接下来的 $d$ 行列出了每个区域中客户的数量和位置，每行一个区域，从第一个区域开始。每行以一个整数 $n$ ($3 \le n \le 8$) 开头，表示该区域内的客户数量，随后是 $n$ 个整数坐标对 $x, y$ ($-10\,000 \le x, y \le 10\,000$)，表示客户的位置。列出的前 $d/2$ 个区域是被裁减销售人员的区域。任意两名客户之间的距离为欧几里得距离，且所有客户的位置各不相同。

输出格式

输出裁员前所有销售巡回路线的总和，以及裁员后所有销售巡回路线的总和。你的答案应精确到绝对误差不超过 $10^{-2}$。

样例

样例输入 1

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

样例输出 1

177.082039 179.442719