Description

你现在在机场，站在 $0$ 点。通往登机口的走廊长度为 $X$ 米，你的飞机即将起飞。走廊上有若干条自动步道，每条步道的速度为 $w_i$。当你在步道上行走或奔跑时，你的速度为（你的速度 $+$ $w_i$）。步道不会移动它们的位置，只是让你移动得更快。步道之间不会重叠：在走廊的任意一点，至多只有一条步道，但一条步道可以在另一条步道结束的地方开始。

你的正常步行速度为 $S$。你担心可能赶不上飞机，因此你可以选择奔跑一段时间——你最多可以以速度 $R$ 奔跑 $t$ 秒。你不需要连续奔跑 $t$ 秒：你可以将这 $t$ 秒分成任意多个时间段，甚至可以不用完全部时间。

请问，在你合理安排步行和奔跑的情况下，最短需要多少时间才能到达登机口 $X$ 点？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为五个整数：$X$（走廊长度，单位为米）、$S$（步行速度，单位为米/秒）、$R$（奔跑速度，单位为米/秒）、$t$（最大奔跑时间，单位为秒）、$N$（步道数量）。

接下来的 $N$ 行，每行包含三个整数：$B_i$、$E_i$ 和 $w_i$，分别表示第 $i$ 条步道的起点、终点（距离起点的米数）以及步道的速度（单位为米/秒）。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试编号（从 $1$ 开始），$y$ 是你到达 $X$ 点所需的最短时间（单位为秒）。当且仅当你的答案的相对或绝对误差不超过 $10^{-6}$ 时，才会被判为正确。

3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1

Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238

Hint

样例解释

在第一个样例中，最优的做法是立即开始奔跑，并奔跑 1 秒。

数据范围

• $1 \leq T \leq 40$。
• $1 \leq S < R \leq 100$。
• $1 \leq w_i \leq 100$。
• $0 \leq B_i < E_i \leq X$。
• $E_i \leq B_{i+1}$。

小数据集（8 分，测试集 1 - 可见）

• $1 \leq t \leq 100$。
• $1 \leq X \leq 100$。
• $1 \leq N \leq 20$。
• 时间限制：3 秒。

大数据集（10 分，测试集 2 - 隐藏）

• $1 \leq t \leq 10^6$。
• $1 \leq X \leq 10^6$。
• $1 \leq N \leq 1000$。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译