#213529. [GCJ 2010 Finals] Travel Plan

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

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 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 to any other planet , consuming units of fuel along the way. It can't turn without landing.

So you need to create a travel plan that requires at most 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, . test cases follow. Each test case description starts with a line containing the number of planets . The next line contains numbers , the coordinates of the planets. The next line contains the amount of fuel that you have.

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

样例输入 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

Limits

• All are different.

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

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