Runaway Quail

All $N$ of your pet quail have gotten loose. You stand at coordinate $0$ on a line. Quail $i$ starts at a nonzero integer coordinate $P_i$, in meters, and runs away from you at the constant integer speed of $S_i$ meters per second. A quail keeps running away even while you are chasing something else. You run at the constant integer speed of $Y$ meters per second and can change direction instantly at any moment. Whenever you occupy the same point as a quail, that quail is caught, and catching it takes no extra time.

Passing a quail requires catching it first, so a quail that starts at a positive coordinate always runs to the right, and a quail that starts at a negative coordinate always runs to the left.

What is the minimum number of seconds needed to catch every quail?

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains two space separated integers $Y$, your speed, and $N$, the number of quail. The next line contains the positions $P_1, P_2, \dots, P_N$, and the line after that contains the speeds $S_1, S_2, \dots, S_N$, each list space separated.

Limits

• $1 \le T \le 100$
• $2 \le Y \le 1000$
• $1 \le N \le 25$
• $-10^7 \le P_i \le 10^7$, $P_i \ne 0$
• $1 \le S_i < Y$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of seconds needed to catch every quail.

Round $y$ to six decimal places and always print six digits after the decimal point. When the discarded part is exactly one half, round up. Every exact answer in the input data is at least $10^{-9}$ away from a rounding boundary.

In test case 1 of the first example, you run to the left and catch all three quail at the same moment, 12 meters to the left of your starting point. That takes 3 seconds.

One optimal strategy for test case 2 is this. Run left and catch the second quail at coordinate $-2$ after one second, then turn around and run right for four more seconds to catch the first quail at coordinate $6$.