Out of gas

Your car is out of gas and you want to get home as quickly as possible. Your home is at the bottom of a hill and your car is at the top of it. The trouble is that another car is right in front of you and you cannot move past it. Your brakes work, and they are very strong.

You start at the top of the hill with speed 0 m/s at time 0 seconds. Gravity pulls your car down the hill with a constant acceleration. At any time you can use the brakes to reduce your speed by any amount, or to reduce your acceleration temporarily by any amount.

Find the shortest time in which you can reach home if you use the brakes in the best possible way.

The first line holds the number of test cases $T$. Then $T$ test cases follow.

The first line of each test case holds three space separated numbers $D$, $N$ and $A$. $D$ is the distance in meters from the top of the hill to your home, given as a real number with exactly 6 decimal places. $N$ and $A$ are integers.

The next $N$ lines hold two space separated real numbers $t_i$ and $x_i$, both with exactly 6 decimal places. $t_i$ is a time in seconds and $x_i$ is a position in meters: at time $t_i$ the other car is $x_i$ meters down the hill from your starting point.

The last line holds $A$ space separated real numbers $a_i$, accelerations in $\mathrm{m/s^2}$, each with exactly 2 decimal places.

The other car travels at a constant speed between time $t_i$ and time $t_{i+1}$. After time $t_{N-1}$ it never comes back up the hill, so its position stays at least $x_{N-1}$.

For example, if $t_5 = 10$, $x_5 = 20$, $t_6 = 20$ and $x_6 = 40$, then 10 seconds after the start the other car is 20 meters down the hill, 15 seconds after the start it is 30 meters down the hill, and 20 seconds after the start it is 40 meters down the hill.

Limits

• $1 \le T \le 20$
• $1.0 \le D \le 10^4$
• $1 \le N \le 1000$
• $1 \le A \le 10$
• $1.00 \le a_i \le 9.81$
• $0.0 \le t_i \le 10^5$
• $0.0 \le x_i \le 10^5$
• $t_0 = 0$, $t_i < t_{i+1}$
• $x_i < x_{i+1}$
• $x_{N-1} \ge D$

For each test case, print a line of the form Case #c:, where $c$ is the test case number starting from 1. Then print $A$ lines. The $i$-th of them holds the minimum number of seconds it takes you to reach home when gravity accelerates you at $a_i$ and you use the brakes in the best possible way.

Round each time at the seventh decimal place and print it with exactly 6 digits after the decimal point. For example, 25 seconds is printed as 25.000000. Print no blank lines.

Position and acceleration. An object with a constant acceleration of $a\ \mathrm{m/s^2}$ and a starting speed of $v_0\ \mathrm{m/s}$ moves a distance of $v_0 t + \frac{1}{2} a t^2$ in $t$ seconds.

Distance on the slope. Every distance and acceleration is measured along the straight line down the hill, not horizontally. If your car accelerates at $2\ \mathrm{m/s^2}$ from a starting speed of $0\ \mathrm{m/s}$ and the other car is stopped at $x = 1$, it takes exactly 1 second to reach the other car.

The other car. You may never pass the other car, so at no time may your distance down the hill be greater than its distance. The two distances may be equal. Treat both cars as point masses.

The brakes. They reduce your speed by any amount at any time, and your speed never becomes negative.