Problem
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 Xi along the line (i = 1, 2, ..., N). Earth is the first planet, lying at coordinate zero, so X1 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 |Xi-Xj| 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.
Input
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 Xi, the coordinates of the planets. The next line contains the amount of fuel F that you have.
Output
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.
Limits
Time limit: 30 5 seconds per test set.
Memory limit: 1GB.
1 ≤ F ≤ 1017.
-1015 ≤ Xi ≤ 1015.
X1=0.
All Xi are different.
Small dataset (Test set 1 - Visible; 3 Points)
1 ≤ T ≤ 100.
2 ≤ N ≤ 10.
Large dataset (Test set 2 - Hidden; 30 Points)
1 ≤ T ≤ 20.
2 ≤ N ≤ 30.
Sample
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