题目描述

Oh no -- your $\mathrm{N}$ pet quail have all gotten loose! You are currently at position 0 on a line; the $\mathrm{i}$ th quail starts off at some nonzero integer (positive or negative) position $\mathbf{P}_{\mathrm{i}}$ on that line, in meters, and will continuously run away from you at a constant integer speed of $\mathbf{S}_{\mathrm{i}}$ meters per second. You can run at a constant integer speed of $\mathrm{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, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each begins with one line with two space-separated integers $\mathrm{Y}$, your speed, and $\mathrm{N}$, the number of quail, and is followed by two more lines with $\mathrm{N}$ space-separated integers each. The first of these gives the positions $\mathbf{P}_{\mathrm{i}}$ of the quail, and the second gives the speeds $\mathbf{S}_{\mathrm{i}}$.

输出格式

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the minimum number of seconds needed to catch all the quail.

$\mathrm{y}$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

2
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1

Case #1: 3.000000
Case #2: 5.000000

提示

Sample Explanation

In Case #1, you can run to the left and catch all three quail at the same time, 12 meters to the left of the starting position, which takes 3 seconds.

In Case #2, one optimal strategy is to run to the left until the second quail is caught at $-2$ m, which takes one second, and then run to the right in pursuit of the first quail, which you will catch at 6 m, taking four more seconds.

Limits

• $1 \leq \mathrm{T} \leq 100 .$
• $2 \leq \mathrm{Y} \leq 1000 .$
• $-10^{7} \leq \mathrm{P}_{\mathrm{i}} \leq 10^{7}$; no $\mathrm{P}_{\mathrm{i}}$ is 0 .
• $1 \leq \mathrm{S}_{\mathrm{i}}<\mathrm{Y} .$

Small dataset(8 Pts)

• Time limit: 240 5 seconds.
• $1 \leq \mathrm{N} \leq 25 .$

Large dataset(15 Pts)

• Time limit: 480 10 seconds.
• $1 \leq \mathrm{N} \leq 500 .$