Bridges#2571
In the country of Lemuria, there are islands connected by bridges. Between each pair of islands numbered and i + 1 (1 \leq i \leq N - 1), there are several parallel bridges. Out of these, exactly a_i bridges are stable, and the remaining b_i bridges are unstable. If a person crosses a stable bridge from island , they reach island i + 1. However, if someone chooses an unstable bridge, it will break before reaching the other side (and, since it is now broken, it will not be considered in the future), and the person falls into the stream and is brought back by the current to island number .
You are initially on island number . Your goal is to reach island number . The strategy is as follows: at each step, randomly choose one of the bridges from the current island to the next one that has not yet been broken, and use it. It is guaranteed that a_i > 0 for all , so you will reach your goal eventually.
The length of each bridge is . Calculate the expected (average) total distance you will travel across all bridges before reaching island , following the strategy described above.
The first line contains an integer (1 \leq N \leq 1000).
The next N - 1 lines each contain two integers a_i and b_i, separated by a space (1 \leq a_i \leq 1000, 0 \leq b_i \leq 1000).
The total number of unstable bridges does not exceed .
Output one real number: the answer to the problem. The absolute or relative error must not exceed 10^{-9}.
Example 1