P13410 [GCJ 2010 Finals] Travel Plan

在南极天文学家尚未公布且正在复查的一项发现中，据说在太空中有 $N$ 个有人居住的行星，这些行星都位于同一直线上，第 $i$ 个行星位于该直线上的坐标 $X_i$ 处（$i = 1, 2, ..., N$）。地球是第一个行星，位于坐标零处，因此 $X_1$ 总是等于 $0$。 你对此感到非常兴奋，开始计划一次访问所有行星的旅行。由于未知的行星可能很危险，你希望每个行星只访问一次，然后返回地球。你有 $F$ 单位的燃料，并希望在这次旅行中尽可能多地消耗燃料，以便最终返回地球时更加安全。你的宇宙飞船非常基础，只能沿直线从任意行星 $i$ 飞到任意行星 $j$，途中会消耗 $|X_i - X_j|$ 单位的燃料。飞船不能在空中转向，必须降落后才能改变方向。 因此，你需要制定一个旅行计划，要求消耗的燃料不超过 $F$ 单位，从地球出发，恰好访问每个其他行星一次，然后返回地球。如果存在多种这样的旅行方案，你应当找到消耗燃料最多的那一种。输出消耗的燃料量。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为行星数量 $N$。下一行为 $N$ 个数 $X_i$，表示各行星的坐标。下一行为你拥有的燃料量 $F$。

对于每个测试用例，输出一行。如果不存在这样的旅行方案，输出 "Case #$x$: NO SOLUTION"；否则输出 "Case #$x$: $y$"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示最大消耗的燃料量。

**数据范围** - $1 \leq F \leq 10^{17}$。 - $-10^{15} \leq X_i \leq 10^{15}$。 - $X_1 = 0$。 - 所有 $X_i$ 坐标互不相同。 **小数据范围（3 分，测试点 1 - 可见）** - $1 \leq T \leq 100$。 - $2 \leq N \leq 10$。 **大数据范围（30 分，测试点 2 - 隐藏）** - $1 \leq T \leq 20$。 - $2 \leq N \leq 30$。 由 ChatGPT 4.1 翻译