糟糕——你的 $N$ 只宠物鹌鹑全都跑丢了！你目前位于直线上坐标为 0 的位置；第 $i$ 只鹌鹑起始于该直线上某个非零整数（正数或负数）坐标 $P_i$（单位：米），并以恒定的整数速度 $S_i$（单位：米/秒）持续远离你。你可以以恒定的整数速度 $Y$（单位：米/秒）奔跑，并且可以随时瞬间改变方向。注意，即使你当时没有朝它们奔跑，鹌鹑也会持续远离你。每当你与某只鹌鹑处于同一位置时，该鹌鹑即被捕获（此过程不消耗额外时间）。

捕获所有鹌鹑所需的最短时间是多少秒？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个空格分隔的整数 $Y$（你的速度）和 $N$（鹌鹑的数量），随后是两行，每行包含 $N$ 个空格分隔的整数。第一行给出鹌鹑的初始位置 $P_i$，第二行给出鹌鹑的速度 $S_i$。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是捕获所有鹌鹑所需的最短时间（秒）。

如果 $y$ 与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。有关详细说明及可接受的实数格式，请参阅 FAQ。

数据范围

$1 \le T \le 100$。 $2 \le Y \le 1000$。 $-10^7 \le P_i \le 10^7$；且 $P_i \neq 0$。 $1 \le S_i < Y$。

子任务

小数据集（8 分）： $1 \le N \le 25$。

大数据集（15 分）： $1 \le N \le 500$。

样例

样例输入 1

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

样例输出 1

Case #1: 3.000000
Case #2: 5.000000

说明

在样例 1 中，你可以向左奔跑，并在起始位置左侧 12 米处同时捕获所有三只鹌鹑，这需要 3 秒。

在样例 2 中，一种最优策略是向左奔跑直到在 -2 米处捕获第二只鹌鹑（耗时 1 秒），然后向右奔跑追赶第一只鹌鹑，并在 6 米处将其捕获，这额外需要 4 秒。