P13165 [GCJ 2017 #1B] Steed 2: Cruise Control

Annie 是一名公交车司机，工作压力很大。她曾尝试通过加勒比海邮轮来放松自己，但那次旅行同样让她感到压力重重，于是她最近开始学习骑马。 今天，Annie 正骑着她的马沿着一条狭长的单向公路向东行进。她现在位于公路的 $0$ 公里处，目的地在 $D$ 公里处；公路上的公里数从西到东依次编号。 在这条路上，还有 $N$ 匹其他马同样向东行进；它们都会一直前进下去，并且目前都位于 Annie 的马和她的目的地之间。第 $i$ 匹马当前位于 $K_i$ 公里处，并以其最大速度 $S_i$ 公里每小时行进。 马非常有礼貌，一匹马 $H_1$ 不会超过（即不会跑到前面去）另一匹起始位置在 $H_1$ 前面的马 $H_2$。（多匹马可以在任意时刻处于同一位置；你可以将马视为一个点。）除 Annie 的马以外，其他马都以最大速度行进，除非某匹马 $H_1$ 追上了另一匹更慢的马 $H_2$，此时 $H_1$ 会减速至 $H_2$ 的速度。 而 Annie 的马没有最大速度限制，她可以选择任意速度，只要不超过其他马。为了让自己和马都能顺利前行，Annie 想为她的马选择一个全程恒定的“巡航速度”，使得她的马在从当前位置到目的地的整个过程中都不会超过其他马。请问她能选择的最大速度是多少？

输入的第一行为测试用例数 $T$；接下来有 $T$ 组测试数据。每组测试数据的第一行为两个整数 $D$ 和 $N$，分别表示所有马的目的地位置（单位：公里）和道路上的其他马的数量。接下来的 $N$ 行，每行包含两个整数 $K_i$ 和 $S_i$，分别表示第 $i$ 匹其他马的初始位置（单位：公里）和最大速度（单位：公里每小时）。

对于每组测试数据，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Annie 能选择的不超过其他马的最大恒定速度（单位：公里每小时）。如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

**样例解释** 在样例 1 中，只有一匹（非常慢的）马在路上；它到达 Annie 目的地需要 $25$ 小时。Annie 选择的速度只要不超过 $101$ 公里每小时，就不会在到达目的地前超过这匹马。 在样例 2 中，有两匹马在路上。较快的马会在 $2$ 小时后于 $240$ 公里处追上较慢的马。此后，两匹马会以较慢马的速度再行进 $1$ 小时，直到到达 $300$ 公里处的目的地。Annie 能选择的最大速度是 $100$ 公里每小时。 **数据范围** - $1 \leq T \leq 100$。 - $0 < K_i < D \leq 10^9$，对所有 $i$。 - $K_i \neq K_j$，对所有 $i \neq j$。（没有两匹马起始位置相同。） - $1 \leq S_i \leq 10000$。 **小数据范围（11 分，测试点 1 - 可见）** - $1 \leq N \leq 2$。 **大数据范围（14 分，测试点 2 - 隐藏）** - $1 \leq N \leq 1000$。 由 ChatGPT 4.1 翻译