Bubbles in liquid P18990

The formulas that describe the vertical speed of a bubble of gas inside a liquid are extremely difficult. Thus, in this problem, we will settle for big simplifications.

0.75 We have $n$ bubbles at several depths. All bubbles are on the same vertical line, separated from one another. Each bubble $i$ is a perfect sphere with radius $r_i$, and its center is at depth $d_i$. Assume that the speed of each bubble is $c \cdot r_i^2$, where $c$ is a given constant. When two bubbles meet (i.e., when they just begin to touch), they instantly merge into a single bubble. The volume of the new bubble is the sum of the volumes of the two previous bubbles. The depth of the center of the new bubble is the center of mass of the two previous bubbles. When a bubble touches the surface of the water, it disappears. Your task is to compute the time it takes for all the bubbles to disappear.

0.19

For instance, consider the first case of the sample input, with a bubble with radius 1 at depth 11, and a bubble with radius 2 at depth 20 (see the first column below). Since $c = 2$, the speed of the smaller bubble is $2 \cdot 1^2 = 2$, and the speed of the larger bubble is $2 \cdot 2^2 = 8$. After exactly one unit of time, the bubbles touch each other (second column), and immediately merge into a single, larger bubble (third column). With some simple computations, we find that the new bubble has radius $\simeq 2.0801$, and its depth is $\simeq 11.6667$. After about 1.1078 more units of time, this bubble reaches the surface of the liquid (fourth column) and disappears.

You can assume that these situations will never happen:

• Two or more consecutive bubbles with the same (or very similar) radii.

• Three or more consecutive bubbles that would disappear at the same (or very similar) moments, with the first touching the second, the second touching the third, and so on.

Input

Input consists of several cases, each with $n$, the real constant $c$, and $n$ pairs of real numbers $d_i$ $r_i$ defining each bubble. Assume $1 \le n \le 10^5$, $c > 0$, and that the bubbles are initially separated and strictly inside the liquid.

Output

For each case, print with 4 digits after the decimal point the time for all the bubbles to disappear. The input cases have no precision issues.