去年，几位热狗摊贩沿着一条街道排成一列，他们使用了一种复杂的算法来分散自己的位置。不幸的是，该算法运行非常缓慢，以至于他们至今仍在移动。不过，一切并没有失去希望：热狗摊贩们制定了一个计划，准备尝试一种新的算法！

问题在于，如果多个摊贩彼此靠得太近，他们就会抢走彼此的生意。摊贩们可以以 $1$ 米/秒的速度沿街道移动。为了避免相互干扰，他们希望站位使得任意两个摊贩之间的距离至少为 $D$ 米。

请记住，街道非常长，因此不用担心在任何方向上空间不足的问题。给定所有热狗摊贩的起始位置，你需要找出所有摊贩达到分散状态（每两个摊贩之间的距离至少为 $D$ 米）所需的最短时间。

输入格式

街道上的每个点都用一个数字标记，可以是正数、负数或零。如果 $p$ 为正，则标记为 $p$ 的点位于标记为 $0$ 的点以东 $|p|$ 米处；如果 $p$ 为负，则位于标记为 $0$ 的点以西 $|p|$ 米处。我们将使用此标记系统在输入文件中描述摊贩的位置。

输入文件的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含起始配置中至少有一个热狗摊贩的点数 $C$ 以及他们希望分散到的最小距离 $D$。接下来的 $C$ 行，每行包含一对以空格分隔的整数 $P$ 和 $V$，表示在标记为 $P$ 的点上有 $V$ 个摊贩。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 $1$ 开始），$y$ 是摊贩在街道上分散开所需的最短时间。相对误差或绝对误差不超过 $10^{-6}$ 的答案将被接受。

样例

输入格式 1

2
3 2
0 1
3 2
6 1
2 2
0 3
1 1

输出格式 1

Case #1: 1.0
Case #2: 2.5