Description

Happy times are always short; this banquet will eventually come to a close.

To leave everyone with a deep and beautiful impression, Suika asked Kawashiro Nitori, who masters cutting-edge technology, to use her newly developed device to light the fireworks.

This device consists of three parts: some ropes of length 1, some ropes of length $\sqrt{ 2 }$, and a nonflammable wooden board. Kawashiro Nitori divides the board into unit cells of side length 1 and marks coordinates. She then lays the ropes on the board to form a connected graph (that is, any two points on the ropes can reach each other). Note that both ends of every rope must be placed on grid vertices: a rope of length 1 can only lie along an edge of a cell, and a rope of length $\sqrt{ 2 }$ can only lie along a diagonal of a cell.

Now, Kawashiro Nitori will ignite the fire at an endpoint of any rope on the board (you cannot light from the middle of a rope). After ignition, the fire propagates along the rope (each rope has its own burning time), and it can ignite any ropes connected to it.

For example, in the figure below, Kawashiro Nitori cannot light at point A, but lighting at point C or point B is allowed.

For the best performance effect, Kawashiro Nitori must minimize the total time until all ropes are completely burned. Because there are too many ropes, she asks you to help compute the minimum total time.

If you can complete this task, you will receive two rewards: 100 points and a grand fireworks show!

Description

Input Format

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

Each of the next n lines contains 5 numbers: X1 Y1 X2 Y2 T, where (X1, Y1) and (X2, Y2) are the coordinates of the two endpoints of a rope, and T is the burning time for this rope when lit from one endpoint until the fire reaches the other endpoint.

Output Format

Output one real number t on the first line, with 4 decimal places, representing the minimum time for all ropes to be completely burned.

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

Hint

[Sample 1 Explanation]: Igniting from either endpoint is fine; the burning time is 1.

[Sample 2 Explanation]:

Ignite at (0, 0). Ropes 1, 3, and 4 will be lit. After 0.5 minutes of burning, rope 2 will be ignited from its midpoint and burn toward both ends. Another 0.5 minutes later, ropes 1, 3, and 4 will be fully burned; rope 5 will be ignited and will finish burning after 1 minute (earlier than rope 2).

After burning from the middle for 0.5 minutes, rope 2 becomes two shorter segments, each with a remaining burning time of 4.5 minutes. But since the other ends of these two segments are also lit at the same time, the burning speed doubles, so they need only 2.25 more minutes. Therefore, the total time is 1 + 2.25 = 3.25.

Constraints:

Translated by ChatGPT 5