Oh no -- your N pet quail have all gotten loose! You are currently at position 0 on a line; the ith quail starts off at some nonzero integer (positive or negative) position P_{i} on that line, in meters, and will continuously run away from you at a constant integer speed of S_{i} meters per second. You can run at a constant integer speed of Y
meters per second, and can change direction instantaneously whenever
you want. Note that quail constantly run away from you even if you are
not running toward them at the time. Whenever you occupy the same point
as a quail, that quail is caught (this takes no additional time).
What is the minimum number of seconds it will take you to catch all of the quail?
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with two space-separated integers Y, your speed, and N, the number of quail, and is followed by two more lines with N space-separated integers each. The first of these gives the positions P_{i} of the quail, and the second gives the speeds S_{i}.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of seconds needed to catch all the quail.
y will be considered correct if it is within an absolute or relative error of 10^{-6} of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
1 ≤ T ≤ 100.
2 ≤ Y ≤ 1000.
-10^{7} ≤ P_{i} ≤ 10^{7}; no P_{i} is 0.
1 ≤ S_{i} < Y.
1 ≤ N ≤ 25.
1 ≤ N ≤ 500.
Input |
Output |
2 4 3 -3 -6 -9 3 2 1 2 2 1 -1 1 1 |
Case #1: 3.000000 Case #2: 5.000000 |
Points | Correct | Attempted |
---|---|---|
8pt | 45 | 107 |
15pt | 16 | 20 |