Description

In a room with both length and width equal to $10$, with the entrance and exit at $(0,5)$ and $(10,5)$ respectively, there are several walls, each with two gaps. Find the shortest path from the entrance to the exit.

Input Format

The first line contains $n$ ($n \le 20$), the number of walls.

The next $n$ lines each contain $5$ real numbers $x, a_1, b_1, a_2, b_2$.

$x$ is the $x$-coordinate of the wall (all walls are vertical). The segments between $a_1 \sim b_1$ and $a_2 \sim b_2$ are openings.

$a_1, b_1, a_2, b_2$ are in increasing order, and $x_1 \sim x_n$ are also in increasing order.

Output Format

Output the shortest distance, keeping $2$ decimal places.

2
4 2 7 8 9
7 3 4.5 6 7

10.06

Hint

Translated by ChatGPT 5