题目描述

小明驾驶飞船对某星系发起攻击。星系中有 $n$ 颗星球，编号依次是 $1, 2, \ldots, n$。第 $i$ 颗星球的坐标为 $(x_i, y_i, z_i)$，且其防御强度为 $w_i$。

小明需要规划出进攻这 $n$ 颗星球的顺序使得其进攻所需能量最少。

对于一个遍历顺序 $p_1, p_2, \ldots, p_n$ 来说，小明进攻需要的能量为 $E = \displaystyle \sum_{i=2}^{n} d(p_{i-1}, p_i) \times w_i$，其中 $d(p_{i-1}, p_i)$ 表示 $p_{i-1}, p_i$ 两颗星球之间的直线距离。小明想知道进攻所需最少能量是多少。

输入格式

输入共 $n + 1$ 行。

第一行为一个正整数 $n$。

后面 $n$ 行，每行四个整数 $x_i, y_i, z_i, w_i$。

输出格式

输出共 $1$ 行，一个浮点数（保留两位小数）。

3
4 3 3 5
2 2 3 5
3 1 1 3

18.53

提示

样例说明

当进攻顺序为 $\{1, 2, 3\}$ 时，所需能量最小，为 $5\sqrt{5} + 3\sqrt{6}$。

评测用例规模与约定

• 对于 $20\%$ 的数据，保证 $n \leq 8$。
• 对于 $100\%$ 的数据，保证 $n \leq 18$，$0 \leq x_i, y_i, z_i, w_i \leq 100$。