Barcelona's trams#1523

Barcelona's trams

1 second

64 megabytes

Hard

Quite recently, the City of Barcelona has included trams in its efficient public transport. As expected, the result has been a nice set of accidents of outstanding originality and beauty. 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}$ \mathbf{P_0} to a final point $P_{n}$ \mathbf{P_n}, visiting the intermediate points $P_{1}, \dots, P_{n - 1}$ \mathbf{P_1}, \ldots, \mathbf{P_{n-1}} in this order. For every $1 \leq i \leq n$ 1 \leq i \leq n, let $S_{i}$ \mathbf{S_i} be the section going from $P_{i - 1}$ \mathbf{P_{i-1}} to $P_{i}$ \mathbf{P_i}. Every such section must be traveled at a uniform speed $v_{i}$ v_i, which is chosen by the driver at $P_{i - 1}$ \mathbf{P_{i-1}}. Let $M_{i}$ M_i be the maximum possible speed of the tram at $S_{i}$ S_i, and assume that the chosen speed is $0 < v_{i} \leq M_{i}$ 0 < v_i \leq M_i. Then, the probability of crashing in $S_{i}$ S_i is $v_{i} / M_{i}$ 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}$ 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}$ 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}$ P_{i-1} and $P_{i}$ P_i, for the sake of computation we can assume that it will take place exactly at the midpoint (after $150$ meters). Therefore, on average, the tram will spend $6$ seconds to reach the midpoint, $10$ seconds to recover from the crash, and $30$ seconds to reach $P_{i}$ 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$ 10 + 10 + 30 = 50 seconds, and with probability $0.4$ it will reach $P_{i}$ P_i after $20$ seconds without any crash. The average time in this case is thus just $0.6 \cdot 50 + 0.4 \cdot 20 = 38$ 0.6 \cdot 50 + 0.4 \cdot 20 = 38 seconds.

When the tram reaches every $P_{i}$ P_i, it stops for a few seconds regardless of having had a crash in $S_{i}$ 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}$ M_0, then we have $M_{i} = M_{0} - C_{i}$ M_i = M_0 - C_i, where $0 \leq C_{i} \leq i - 1$ 0 \leq C_i \leq i-1 is the total number of crashes suffered in $S_{1}, \dots, S_{i - 1}$ S_1, \ldots, 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

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

Output

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

Examples

Example 1