题目描述

在一个二维平面上有 $N$ 个城市。第 $i$ 个城市的坐标为 $(x_i, y_i)$ ，初始时该城市储存的水量为 $a_i$ 升。

Snuke 可以从一个城市携带任意数量的水到另一个城市。然而，在他携带水的过程中，会有一些水泄漏出来。如果他从第 $s$ 个城市携带 $l$ 升水到第 $t$ 个城市，那么当他到达目的地时，只剩下 $max(l-d_{s,t}, 0)$ 升水。其中 $d_{s,t}$ 表示第 $s$ 个城市和第 $t$ 个城市之间的（欧几里得）距离。他可以执行任意次数的此类操作。

Snuke 希望最大化 $N$ 个城市中的最小水量。找到最大的 $X$ ，使得他至少能向每个城市分配 $X$ 升水。

约束条件

• $1 ≤ N ≤ 15$
• $0 ≤ x_i, y_i, a_i ≤ 10^9$
• 输入中的所有值都是整数。
• 没有两个城市处于同一个位置。

输入

输入以以下格式从标准输入中给出：

$N$ $x_1$ $y_1$ $a_1$ : $x_N$ $y_N$ $a_N$

输出

输出 $N$ 个城市中最小水量的最大值。绝对误差或相对误差必须小于 $10^{-9}$。

输入示例1

3
0 0 10
2 0 5
0 5 8

输出示例1

6.500000000000

最优解是从第一个城市携带 3.5 升水到第二个城市。操作完成后，第一个城市和第二个城市都会有 6.5 升水，而第三个城市会有 8 升水。

输入示例2

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447

输出示例2

434666178.237122833729