Description

去年，有几位热狗摊贩沿着一条街道排成一列，他们采用了一种复杂的算法来分散自己。不幸的是，这个算法非常慢，他们至今还没有分散好。不过，一切还没有结束！热狗摊贩们有了一个新计划：是时候尝试一种新算法了！

问题在于，多个摊贩可能站得太近，这样他们就会互相抢生意。摊贩们可以以每秒 $1$ 米的速度沿街道移动。为了避免互相干扰，他们希望每对摊贩之间的距离至少为 $D$ 米。

请注意，这条街道非常长，所以无论往哪个方向移动都不会遇到空间不足的问题。给定所有热狗摊贩的初始位置，请你计算出所有摊贩分散开（任意两名摊贩之间的距离至少为 $D$ 米）所需的最短时间。

Input Format

街道上的每个点都用一个数字标记，可能为正、负或零。标记为 $p$ 的点，若 $p$ 为正，则在标记为 $0$ 的点以东 $|p|$ 米处；若 $p$ 为负，则在标记为 $0$ 的点以西 $|p|$ 米处。我们将使用这种标记方式来描述输入文件中摊贩的位置。

输入文件的第一行包含测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行包含两个整数 $C$ 和 $D$，分别表示初始时有摊贩的点的数量，以及他们希望分散到的最小距离。接下来的 $C$ 行，每行包含两个用空格分隔的整数 $P$ 和 $V$，表示在标记为 $P$ 的点上有 $V$ 个摊贩。

Output Format

对于每组测试数据，输出一行，格式为 “Case #$x$: $y$”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是所有摊贩分散开所需的最短时间。只要你的答案的相对或绝对误差不超过 $10^{-6}$，即可被接受。

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

Hint

数据范围

• $1 \leq T \leq 50$。
• 所有 $P$ 的取值范围为 $[-10^5, 10^5]$。
• 每组测试数据中所有 $P$ 互不相同，且按递增顺序给出。每组测试数据中所有 $V$ 的和见下文。所有 $V$ 都是正整数。

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

• $1 \leq D \leq 5$
• $1 \leq C \leq 20$
• 每组测试数据中所有 $V$ 的和不超过 $100$
• 时间限制：3 秒

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

• $1 \leq D \leq 10^6$
• $1 \leq C \leq 200$
• 每组测试数据中所有 $V$ 的和不超过 $10^6$
• 时间限制：6 秒

由 ChatGPT 4.1 翻译