An ironman triathlon is a race where participants swim for
$3.86$ km, ride a bicycle
for $180.25$ km, and
finally run a marathon, and it is considered one of the
toughest sport events. Viveka has been training for an even
more challenging competition: the $n$athlon. In an $n$athlon race, participants have to
go from the starting point to the finishing point through
several types of terrain: water, sand, ice, asphalt, etc. To
make the race more interesting, participants are free to pick
the route that they think suits best their abilities. Last year
Viveka achieved an epic victory by skating the last
$40$ km in $1$ hour over ice, while her
archrival Veronica was stuck in a tar pit $1$ m from the finishing point.
The terrain distribution for this year has been published
and now it is your task as the optimization expert in Viveka’s
team to help her figure out the best route for the race. The
competition takes place in a flat area, which we model as the
2D plane, and each type of terrain is shaped as a horizontal
strip. Participants are not allowed to leave the race area. You
know the position of each strip and Viveka’s speed in that type
of terrain.
Input
The first line contains two pairs of decimal numbers
$x_ s$, $y_ s$, $x_ f$, $y_ f$, the $x$ and $y$ coordinates of the starting and
finishing point, respectively, in meters. The second line
contains one integer $n$
($1 \leq n \leq 10\,
000$), the number of layers. The third line contains
$n1$ decimal numbers, the
$y$ coordinate of each
change between layers. Layers are given in order, that is,
$y_ s < y_1 < y_2 <
\cdots < y_{n1} < y_ f$, so the shape of layer
$i$ is $(10\, 000,10\, 000)\times
(y_{i1},y_{i})$. The first and last layers extend only
until the $y$ coordinate
of the starting and finishing point, this is they have shape
$(10\, 000,10\, 000)\times (y_
s,y_1)$ and $(10\,
000,10\, 000)\times (y_{n1},y_ f)$ respectively. The
fourth line contains $n$
decimal numbers, Viveka’s speed in each layer, in meters per
second. All decimal numbers have absolute value at most
$10^4$ and at most
$4$ decimals.
Output
Output the minimum time required for Viveka to go from the
starting to the finishing point. Your answer should be within
absolute or relative error at most $10^{6}$.
Sample Input 1 
Sample Output 1 
0 0 0 100
2
50
5 1

60

Sample Input 2 
Sample Output 2 
0 0 100 100
2
50
1 5

71.5697725691
