Description

哦不——你的 $N$ 只鹌鹑全都跑掉了！你现在位于一条直线上的 $0$ 位置；第 $i$ 只鹌鹑一开始在该直线上的某个非零整数位置 $P_i$（可以为正也可以为负，单位为米），并且会以恒定的整数速度 $S_i$ 米每秒不断地远离你奔跑。你可以以恒定的整数速度 $Y$ 米每秒奔跑，并且可以随时瞬间改变方向。注意，即使你没有朝着某只鹌鹑奔跑，鹌鹑也会一直远离你。当你和某只鹌鹑处于同一位置时，你就能抓住它（不需要额外时间）。

你需要用最少多少秒才能抓住所有的鹌鹑？

Input Format

输入的第一行是测试用例的数量 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为两个用空格分隔的整数 $Y$（你的速度）和 $N$（鹌鹑的数量），接下来两行各有 $N$ 个用空格分隔的整数。第一行为各只鹌鹑的初始位置 $P_i$，第二行为各只鹌鹑的速度 $S_i$。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为抓住所有鹌鹑所需的最少秒数。

如果你的答案 $y$ 与正确答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

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

Case #1: 3.000000
Case #2: 5.000000

Hint

样例解释

在第 1 组样例中，你可以向左跑，在距离起点左侧 12 米处同时抓住三只鹌鹑，用时 3 秒。

在第 2 组样例中，一种最优策略是先向左跑，1 秒后在 $-2$ 米处抓住第二只鹌鹑，然后掉头向右追第一只鹌鹑，在 6 米处抓住它，总共用时 4 秒。

数据范围

• $1 \leq T \leq 100$。
• $2 \leq Y \leq 1000$。
• $-10^7 \leq P_i \leq 10^7$，且所有 $P_i$ 均不为 0。
• $1 \leq S_i < Y$。

小数据集（8 分）

• 时间限制：5 秒。
• $1 \leq N \leq 25$。

大数据集（15 分）

• 时间限制：10 秒。
• $1 \leq N \leq 500$。

由 ChatGPT 4.1 翻译