问题描述

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

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

对于一个遍历顺序 $p_1,p_2,...,p_n$​ 来说，小明进攻需要的能量为 $E=\sum_{i=2}^nd(p_{i−1},p_i)×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\sqrt5+3\sqrt6$​。

评测用例规模与约定

对于 $20\%$ 的数据，保证 $n≤8$。

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