背景

宴会已经接近尾声。 :::align{center} :::

题目描述

快乐的时光总是这么短暂，这场宴会终究将要闭幕。

为了给大家留下一个深刻而美好的印象，萃香拜托掌握着顶尖科技的河城荷取用她刚刚研制出的装置来点燃烟花。

这个装置由 $3$ 部分构成 —— 一些长度为 $1$ 的绳子，一些长度为 $\sqrt2$ 的绳子，还有一块不能燃烧的木板。河城荷取将木板划分成长度为 $1$ 的单元格，并标上坐标，之后将这些绳子摆在木板上连接成一个连通图（即绳子上的任意两点均可互相到达）。注意，这些绳子的两端必须放在单元格的顶点上，即长度为 $1$ 的绳子只能放在单元格的某一边上，长度为 $\sqrt2$ 的绳子只能放在单元格的某一对角线上。

现在，河城荷取会在木板上任意一根绳子的端点处点火(不能从绳子的中间处点火)，点火后，火会沿着绳子向前燃烧（每根绳子都有自己的燃烧速度），并能点燃与它相接的其它绳子。

比如说下面这张图，河城荷取不能在 $\text A$ 点点火，但在 $\text C$ 点或 $\text B$ 点点火都是充许的。

:::align{center} :::

为了演出效果，河城荷取必须保证所有绳子都燃烧完的总时间最短，可是由于绳子的条数过多，所以河城荷取找到了你来帮忙，让你帮她求出最短的总时间是多少。

如果你能完成这个任务，你就会获得两个奖励 —— $100$ 分和观赏一场盛大的烟花盛宴！

输入格式

第一行为一个正整数 $n$，表示绳子的条数。

接下来 $n$ 行每行 $5$ 个数 $X_1,Y_1,X_2,Y_2,T$，其中 $(X_1,Y_1)$ 和 $(X_2,Y_2)$ 分别表示绳子两端的坐标， $T$ 表示这根绳子的燃烧时间，是指从绳子的某一端点火燃烧到另一端，燃完所需的时间。

输出格式

第一行一个实数 $t$，保留 $4$ 位小数，表示所有绳子完全燃烧的最少时间。

1
0 0 1 1 1

1.0000

5
0 0 0 1 1
1 0 0 1 10
0 0 1 0 1
0 0 1 1 1
2 2 1 1 1

3.2500

提示

【样例 #1 解释】

从任一端点火都行，燃烧时间都是 $1$。

【样例 #2 解释】

在 $(0,0)$ 位置点火，绳子 $1,3$ 和 $4$ 将被点燃，燃烧 $0.5$ 分钟后，绳子 $2$ 将被从中间点燃向两端燃烧，再过 $0.5$ 分钟，绳子 $1,3,4$ 将被完全燃烧，绳子 $5$ 将被点燃并在 $1$ 分钟后燃烧完 (比绳子 $2$ 早燃完)。

绳子 $2$ 从中间向两端燃烧 $0.5$ 分钟以后，变成两小段，每段的燃烧时间是 $4.5$ 分钟。但因为此时两小段绳子的另一端也同时被点燃，燃烧速度变成原来的两倍，还需 $2.25$ 分钟的燃烧时间，所以总时间如下。

【数据规模与约定】

::cute-table{tuack} | 测试点编号 | $n$ | $T$ | $X,Y$ | |:-:|:-:|:-:|:-:| | $1$ | $1\leq n\leq 10$ | $1\leq n\leq 10$ | $-10^3\leq X,Y\leq 10^3$ | | $2$ | $1\leq n\leq 20$ | $1\leq n\leq 100$ | ^ | | $3$ | $1\leq n\leq 30$ | $1\leq n\leq 10^3$ | ^ | | $4$ | $1\leq n\leq 50$ | $1\leq n\leq 10^4$ | ^ | | $5$ | ^ | ^ | ^ | | $6$ | ^ | ^ | ^ | | $7$ | ^ | ^ | ^ | | $8$ | ^ | ^ | ^ | | $9$ | ^ | ^ | ^ | | $10$ | ^ | ^ | ^ | | $11$ | $1\leq n\leq 100$ | ^ | ^ | | $12$ | ^ | ^ | ^ | | $13$ | ^ | ^ | ^ | | $14$ | ^ | $1\leq n\leq 10^5$ | ^ | | $15$ | $1\leq n\leq 400$ | ^ | ^ | | $16$ | ^ | ^ | ^ | | $17$ | ^ | ^ | ^ | | $18$ | ^ | ^ | ^ | | $19$ | ^ | ^ | ^ | | $20$ | ^ | ^ | ^ |