Quite recently, the City of Barcelona has included trams to its “efficient” public transport. As expected, the result has been a nice set of accidents of outstanding originality and beauty. But diminishing aesthetic reasons, the Mayor of Barcelona has decided to reduce the delay caused by the accidents. After a thorough study the following model has been established.

Every tram must go from an initial point P_{0} to a final point P_{n}
visiting the intermediate points P_{1}, …, P_{n−1} in this order.
For every 1 ≤ i ≤ n,
let S_{i} be the section that goes from P_{i−1} to P_{i}.
Every such section must be travelled at uniform speed v_{i},
which is chosen by the driver at P_{i−1}.
Let M_{i} be the maximum possible speed of the tram at S_{i},
and assume that the chosen speed is 0 < v_{i} ≤ M_{i}.
Then the probability of crashing in S_{i} is v_{i}/M_{i}.
When a crash happens,
the tram uses an efficient recovery system that lasts only 10 seconds.
Afterwards, the tram reaches P_{i} using an auxiliary (slow but safe) engine,
which provides a speed of 5 meters per second
and guarantees no more crashes in S_{i}.

For instance, assume that the section length is 300 meters,
and that the current maximum speed is 25 meters per second.
If the driver chooses to travel at 25 m/s,
the tram will crash for sure.
Since this can happen anywhere between P_{i−1} and P_{i},
for the sake of computation
we can assume that it will take place exactly in the middle point
(after 150 meters).
Therefore, on the average
the tram will spend 6 seconds to reach the middle point,
10 seconds to recover from the crash,
and 30 seconds to reach P_{i},
for a total of 46 seconds.
By contrast, if the tram starts traveling at 15 m/s,
with probability 0.6
it will crash and spend 10 + 10 + 30 = 50 seconds,
and with probability 0.4
it will reach P_{i} after 20 seconds without any crash.
The average time in this case is thus
just 0.6*50 + 0.4*20 = 38 seconds.

When the tram reaches every P_{i}, it stops for a few seconds
regardless of having crashed in S_{i} or not;
these few seconds (for simplicity, we consider them to be 0)
are enough to (almost) repair the tram:
the maximum speed reduces by 1 m/s after every crash.
In other words, if we call the initial maximum speed M_{0},
then we have M_{i} = M_{0} − C_{i},
where 0 ≤ C_{i} ≤ i−1 is the total number of crashes
suffered in S_{1}, …, S_{i−1}.

Write a program to print the optimal average travel time given the initial maximum speed and the length of every section.

[r]

Input

Input consists of several cases,
each one with M_{0} (a real number between 5 and 1000),
n (an integer number between 1 and M_{0} − 1),
and the length of every section
(each one a real number between 100 and 1000).

0

Output

For every case, print the optimal average travel time with four digits after the decimal point. The input cases have no precision issues.

Public test cases

**Input**

25 1 900 25 2 900 900 25 2 305.15 980.76 5 1 1000

**Output**

102.0000 205.0303 150.0000 210.0000

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++