南极天文学家在一项尚未公布且经过复核的发现中写道，太空中存在 $N$ 个宜居行星，它们都位于同一条直线上，第 $i$ 个行星位于该直线上的坐标 $X_i$ 处（$i = 1, 2, \dots, 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 \le F \le 10^{17}$ $-10^{15} \le X_i \le 10^{15}$ $X_1 = 0$ 所有 $X_i$ 互不相同。

子任务

小型数据集（测试集 1 - 可见；3 分）： $1 \le T \le 100$ $2 \le N \le 10$

大型数据集（测试集 2 - 隐藏；30 分）： $1 \le T \le 20$ $2 \le N \le 30$

样例

样例输入 1

3
3
0 10 -10
40
5
0 1 2 3 4
13
5
0 1 2 3 4
7

样例输出 1

Case #1: 40
Case #2: 12
Case #3: NO SOLUTION