eolymp
bolt
Try our new interface for solving problems
Problems

Barcelona`s trams

Barcelona`s trams

Time limit 1 second
Memory limit 64 MiB

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. Diminishing aesthetic reasons, the Major 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 1in, let S_i be the section going from P_{i-1} to P_i. Every such section must be traveled 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_iM_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 the crash 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 had a crash 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. If we call the initial maximum speed M_0, then we have M_i = M_0 - C_i, where 0C_ii-1 is the total number of crashes suffered in S_1, ..., S_{i-1}.

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

Input data

Each line corresponds to one test case and contains the initial maximum speed M_0 (a real number between 5 and 25), the value of n (an integer number between 1 and M_0 - 1), and the length of every section (each is a real number between 100 and 1000).

Output data

For every test case, print the optimal average travel time with four decimal digits.

Examples

Input example #1
25 1 900
25 2 900 900
25 2 305.15 980.76
5 1 1000
Output example #1
102.0000
205.0303
150.0000
210.0000