Barcelona's trams P38716

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₀ to a final point P_n visiting the intermediate points P₁, …, 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₀, then we have M_i = M₀ − C_i, where 0 ≤ C_i ≤ i−1 is the total number of crashes suffered in S₁, …, 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₀ (a real number between 5 and 1000), n (an integer number between 1 and M₀ − 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.