AT_arc229_f [ARC229F] Angst for All Pairs 2

You are given a positive integer $ N $ and a length- $ N $ sequence of positive integers $ C=(C_1,C_2,\ldots,C_N) $ . You want to prepare one or more cards, as many as you like, and write one integer between $ 1 $ and $ N $ (inclusive) on each of the front and back sides of each card, so that the following condition is satisfied. - No matter which distinct integers $ x $ and $ y $ between $ 1 $ and $ N $ (inclusive) are chosen, there exists at least one card satisfying the following. - Exactly one of $ x $ and $ y $ is written on at least one side of that card. It is allowed to write the same integer on the front and back of a single card. Here, the cost of writing $ a $ on the front and $ b $ on the back of a card is $ C_a+C_b $ . Find the minimum total cost required to satisfy the condition. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. By creating a card with $ 1 $ written on the front and $ 2 $ on the back, and a card with $ 2 $ written on the front and $ 2 $ on the back, the condition can be satisfied. The total cost in this case is $ 3+2+2+2=9 $ . It is impossible to satisfy the condition with a total cost less than $ 9 $ , so output $ 9 $ on the first line. ### Constraints - $ 1\le T\le 10^5 $ - $ 2\le N\le 2\times 10^5 $ - $ 1\le C_i\le 10^9 $ - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ . - All input values are integers.