AT_arc229_f [ARC229F] Angst for All Pairs 2

正整数 $ N $ と長さ $ N $ の正整数列 $ C=(C_1,C_2,\ldots,C_N) $ が与えられます。 カードを $ 1 $ 枚以上好きな枚数用意し、それぞれのカードの表と裏に $ 1 $ 以上 $ N $ 以下の整数を $ 1 $ つずつ書き込むことで、以下の条件を満たすようにしたいです。 - $ 1 $ 以上 $ N $ 以下の相異なる整数 $ x,y $ をどのように選んでも、以下を満たすカードが $ 1 $ 枚以上存在する。 - $ x,y $ のうちちょうど一方が、そのカードの少なくとも一方の面に書かれている。 $ 1 $ 枚のカードの表と裏に同じ整数を書き込むことも許されます。 ただし、 $ 1 $ 枚のカードの表に $ a $ を、裏に $ b $ を書き込むためにはコストが $ C_a+C_b $ かかります。 条件を満たすために必要なコストの総和の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 表に $ 1 $ を、裏に $ 2 $ を書き込んだカードと、表に $ 2 $ を、裏に $ 2 $ を書き込んだカードを作ることで条件を満たすことができます。 この際のコストの総和は $ 3+2+2+2=9 $ です。コストの総和が $ 9 $ 未満で条件を満たすことはできないので、 $ 1 $ 行目には $ 9 $ を出力してください。 ### Constraints - $ 1\le T\le 10^5 $ - $ 2\le N\le 2\times 10^5 $ - $ 1\le C_i\le 10^9 $ - 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力される値は全て整数