题目描述

In a yet-to-be-announced and rechecked discovery by Antarctic astronomers, it is written that there are $N$ inhabited planets in space, all lying along the same straight line, with the $i$-th planet lying at coordinate $X_i$ along the line ($i = 1, 2, ..., N$). Earth is the first planet, lying at coordinate zero, so $X_1$ will always be equal to $0$.

Being very excited about this fact, you start planning a trip to visit all the planets. Since unknown planets can be dangerous, you want to visit each planet exactly once before returning to Earth. You have $F$ units of fuel, and you want to spend as much of it on this trip as possible so that your final landing on Earth is safer. Your spaceship is pretty basic and can only fly along a straight line from any planet $i$ to any other planet $j$, consuming $|X_i - X_j|$ units of fuel along the way. It can't turn without landing.

So you need to create a travel plan that requires at most $F$ units of fuel, starts from Earth, visits each of the other planets exactly once, and then returns to Earth. If there are several such plans, you should find the one that consumes most fuel. Output the amount of fuel consumed.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case description starts with a line containing the number of planets $N$. The next line contains $N$ numbers $X_i$, the coordinates of the planets. The next line contains the amount of fuel $F$ that you have.

输出格式

For each test case, output one line containing either "Case #$x$: NO SOLUTION", when there's no such travel plan, or "Case #$x$: $y$", where $x$ is the case number (starting from $1$) and $y$ is the maximum amount of fuel consumed.

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

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

提示

Limits

• $1 \leq F \leq 10^{17}.$
• $-10^{15} \leq X_i \leq 10^{15}.$
• $X_1 = 0.$
• All $X_i$ are different.

Small dataset (3 Pts, Test set 1 - Visible)

• $1 \leq T \leq 100.$
• $2 \leq N \leq 10.$

Large dataset (30 Pts, Test set 2 - Hidden)

• $1 \leq T \leq 20.$
• $2 \leq N \leq 30.$