题目描述

你的车没油了，你想尽快回到家！幸运的是，你的家在山脚下，而你（在车里）在山顶。不幸的是，你前面有一辆车，你无法超越它。幸运的是，你的刹车功能正常，而且非常强劲。

你从山顶出发，在时间为 0 秒时速度为 0 m/s。重力以恒定的加速度将你的车向山下牵引。在任何时刻，你都可以使用刹车来降低速度，或者通过任何方式暂时减小加速度。

如果你以最优的方式使用刹车，你最快能多快到达家？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个空格分隔的数字：一个实数 $D$，表示到山脚下家的距离（单位：米）；以及两个整数 $N$ 和 $A$。距离 $D$ 将以精确的 6 位小数给出。

接下来 $N$ 行，每行包含两个空格分隔的实数：时间 $t_i$（单位：秒）和位置 $x_i$（单位：米）。$t_i$ 和 $x_i$ 的值将以精确的 6 位小数给出。

最后一行包含 $A$ 个空格分隔的实数 $a_i$，表示加速度（单位：$m/s^2$）。加速度将以精确的 2 位小数给出。

前车的行驶位置由 $(t_i, x_i)$ 对指定。该车在时间 $t_i$ 秒时的位置是距离山顶（即你的初始位置）$x_i$ 米处。该车在时间 $t_i$ 和 $t_{i+1}$ 之间以恒定速度行驶。位置和时间均按递增顺序给出，且 $t_0=0$。

例如，如果 $t_5=10, x_5=20, t_6=20, x_6=40$，那么在出发后 10 秒，前车在山下 20 米处；出发后 15 秒，前车在山下 30 米处；出发后 20 秒，前车在山下 40 米处。

输出格式

对于每个测试用例，输出一行 "Case #c:"，其中 $c$ 是用例编号（从 1 开始）。然后输出 $A$ 行，第 $i$ 行包含当你受重力影响的加速度为 $a_i$ 且以最优方式使用刹车时，到达家所需的最短时间（单位：秒）。答案与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内均被接受。输出中不应包含空行。

说明

位置与加速度： 一个具有恒定加速度 $a \, m/s^2$ 且初始速度为 $v_0 \, m/s$ 的物体，在 $t$ 秒后移动的距离为 $v_0 \cdot t + 0.5 \cdot a \cdot t^2$。

坡道距离： 所有距离和加速度均相对于沿山坡的直线给出。它们不是水平距离；因此，如果你的车以 $0 \, m/s$ 的初速度加速 $2 \, m/s^2$，而前车在 $x=1$ 处停止，那么到达前车将正好需要 1 秒。

前车： 你永远不能超过前车，这意味着在任何时刻，你距离山顶的距离都不得大于前车的距离。可以相等。两辆车均视为质点。

输出值： 你可以在输出中打印任意位小数。我们将读取并与我们的答案进行比较，比较时将使用 $10^{-6}$ 作为误差阈值。因此，从我们的角度来看，25、25.0 和 25.000000 是相同的。小数点后的尾随零不影响结果。

数据范围

$1 \le T \le 20$

$1.0 \le D \le 10^4$

$1.0 \le a_i \le 9.81$

$0.0 \le t_i \le 10^5$

$0.0 \le x_i \le 10^5$

$t_i < t_{i+1}$

$x_i < x_{i+1}$

$t_0 = 0$

$x_{N-1} \ge D$

子任务 1

$1 \le N \le 2$

$1 \le A \le 10$

子任务 2

$1 \le N \le 2000$

$1 \le A \le 250$

样例

输入 1

3
1000.000000 2 3
0.000000 20.500000
25.000000 1000.000000
1.00 5.00 9.81
50.000000 2 2
0.000000 0.000000
100000.000000 100.000000
1.00 1.01
10000.000000 3 1
0.000000 0.000000
10000.000000 0.100000
10000.100000 100000.000000
1.00

输出 1

Case #1:
44.7213595
25.000000
25.0
Case #2:
50000.0
50000.0
Case #3:
10140.974143