Problem Description

The banquet is drawing to a close.

To leave a deep and beautiful impression, Suika asked Kawashiro Nitori, who possesses top-notch technology, to use her newly developed device to ignite the fireworks.

The device consists of three parts—ropes of length 1, ropes of length $\sqrt{2}$, and a non-combustible wooden board. Nitori divided the board into unit squares of length 1 and labeled them with coordinates. Then, she placed these ropes on the board to form a connected graph (i.e., any two points on the ropes can reach each other). Note that the ends of these ropes must be placed on the vertices of the unit squares. That is, ropes of length 1 can only be placed along the edges of the squares, and ropes of length $\sqrt{2}$ can only be placed along the diagonals of the squares.

Now, Nitori will ignite the device at one of the endpoints of any rope on the board (ignition cannot occur in the middle of a rope). Once ignited, the fire will burn along the rope (each rope has its own burning speed) and can ignite other connected ropes.

For example, in the following diagram, Nitori cannot ignite the fire at point A, but igniting at point C or B is allowed.

For the performance, Nitori must ensure that the total time for all ropes to burn out is the shortest. However, due to the large number of ropes, she has asked for your help to calculate the shortest total time.

If you can accomplish this task, you will receive two rewards—100 points and the opportunity to watch a grand fireworks display!

Input Format

The first line contains a positive integer n, representing the number of ropes.

The next n lines each contain 5 numbers: X1 Y1 X2 Y2 T, where (X1, Y1) and (X2, Y2) represent the coordinates of the two ends of the rope, and T represents the burning time of the rope, which is the time required to burn from one end to the other.

Output Format

The first line contains a real number t, rounded to 4 decimal places, representing the minimum total time for all ropes to burn completely.

Sample Input and Output

Sample Input #1

1
0 0 1 1 1

Sample Output #1

1.0000

Sample Input #2

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

Sample Output #2

3.2500

Notes

Sample 1 Explanation: Igniting at either end will result in a burning time of 1.

Sample 2 Explanation:

Igniting at the (0,0) position will light ropes 1, 3, and 4. After 0.5 minutes, rope 2 will be ignited from the middle and burn towards both ends. After another 0.5 minutes, ropes 1, 3, and 4 will be completely burned, and rope 5 will be ignited and burn out in 1 minute (earlier than rope 2).

Rope 2, burning from the middle towards both ends for 0.5 minutes, splits into two shorter segments, each with a burning time of 4.5 minutes. However, since both ends of these segments are ignited simultaneously, the burning speed doubles, requiring an additional 2.25 minutes. Therefore, the total time is: 1 + 2.25 = 3.25.

Data Range:

见题面 Input 部分

见题面 Output 部分