P13230 [GCJ 2015 #3] Runaway Quail

哦不——你的 $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}$，则视为正确。

**样例解释** 在第 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 翻译