There's a famous bridge puzzle, where you have four persons, each with a unique time required to cross the bridge. The bridge is a wooden one floating over a very deep valley and the time is night, so it's very dark. You need to use a lantern so that you don't miss a step and fall into the valley (No one has ever survived a fall from there and there's only one lantern available). After one or two person crossed the bridge with the lantern they need to return the lantern to the other side of the bridge so that others can use it to cross the bridge. Also, the bridge is an old one and very weak. Thus more than two persons on the bridge may collapse the bridge taking everyone on it down to the bottom of the valley. Moreover, when two persons are crossing the bridge the time required will be equal to the maximum of their individual required time. In the puzzle, there's a given time limit within which you need to cross the bridge and also mention the way to cross the bridge.
Now this problem is an extended version of the main puzzle. Here you have n person, each with a unique required time to cross the bridge. You have to print the minimum time required for n persons to cross the bridge in the above-mentioned way.
Input
Input starts with an integer T (0<T<101) denoting the number of test cases. Each test case begins with an integer n (0<n<50001). Then there will be n unique integers in the next line, each of which will be greater than 0 and no more than 108. These n integers represent the time required by each of the n individuals.
Output
For each case, print the case number and the minimum time required to cross the bridge in the above-mentioned manner.
Sample
| Input | Output |
|---|---|
1 4 1 4 5 10 | Case 1: 21 |
