Travel Plan (Large)

Antarctic astronomers have an observation they have not announced yet: space holds $N$ inhabited planets, and all of them lie on one straight line. The $i$-th planet sits at coordinate $X_i$. Earth is the first planet and sits at coordinate 0, so $X_1 = 0$.

Excited by this, you plan a trip that visits all of them. Unknown planets are dangerous, so you leave Earth, visit each of the other planets exactly once, and return to Earth. You have $F$ units of fuel, and you want to burn as much of it as you can so that the final landing on Earth is safer. Your spaceship is basic. It flies in a straight line from a planet $i$ to another planet $j$ and burns $|X_i - X_j|$ units of fuel on the way, and it cannot turn without landing.

Among the travel plans that burn at most $F$ units of fuel, find the one that burns the most, and print the amount of fuel it burns.

The first line contains the number of test cases $T$. Each test case takes three lines. The first line contains the number of planets $N$. The second line contains the coordinates $X_1, X_2, \dots, X_N$. The third line contains the amount of fuel $F$ that you have.

Limits

• $1 \le T \le 20$
• $2 \le N \le 30$
• $1 \le F \le 10^{17}$
• $-10^{15} \le X_i \le 10^{15}$
• $X_1 = 0$
• All $X_i$ are different.

For each test case, print one line. Print Case #x: NO SOLUTION when no such travel plan exists, and Case #x: y otherwise, where $x$ is the test case number starting from 1 and $y$ is the largest amount of fuel a plan burns.