Runaway Quail

All $N$ of your pet quail have gotten loose. You stand at position $0$ on a number line, and quail $i$ starts at a nonzero integer position $P_i$, measured in meters. Every quail runs away from the point where you are at a constant speed of $S_i$ meters per second, and it keeps running even while you are not chasing it.

You run at a constant speed of $Y$ meters per second and you reverse direction instantly whenever you want. The moment you occupy the same point as a quail, that quail is caught, and catching it takes no extra time.

What is the minimum number of seconds it takes 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 your speed $Y$ and the number of quail $N$, separated by a space. The second line contains the positions $P_1, \dots, P_N$ and the third line contains the speeds $S_1, \dots, S_N$, each separated by spaces.

Limits

• $1 \le T \le 100$
• $2 \le Y \le 100$
• $1 \le N \le 500$
• $-10^4 \le P_i \le 10^4$ and $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$ at the seventh digit after the decimal point and print exactly six digits after the decimal point. In every test file the answer is at least $5 \times 10^{-9}$ away from a value where that rounding would go either way.