\(C\) が昇順にソートされているとします。また、同じ組 \((a,b)\) のカードを複数枚用意しても条件には寄与しないため、同じ辺を複数本張らないとします。

\(N\) 頂点のグラフを考え、\(1\) 枚のカードの表に \(a\) を、裏に \(b\) を書き込むことを頂点 \(a\) と頂点 \(b\) を繋ぐ無向辺を作ることと対応付けます。すると、条件は以下に言い換えられます：

• グラフに孤立点（次数が \(0\) の頂点）が \(1\) 個以下である。
• 頂点数が \(2\) で辺数が \(1\) の連結成分が存在しない。

コストの最小化を考える上で孤立点は \(1\) 個存在した方が良いので、頂点 \(N\) が孤立点であるとして良いです。以降は \(N'=N-1\) 頂点で後者の条件のみを考えた場合の最小化を考えます。

まず、\(N'\) 頂点が全て連結となるようにする場合のコストの総和の最小値を考えます。（以降コストの総和の最小値も単にコストと呼びます。）

\(N'=1\) の場合は孤立点が存在しないという条件から自己辺を作る必要があり、コストは \(2C_1\) です。また、\(N'=2\) の場合は辺数が \(2\) 以上である必要があるためコストは \(3C_1+C_2\) です。\(N'\geq 3\) である場合は頂点 \(1\) に全て繋ぐのが最適で、コストは \(\displaystyle (N'-1)C_1+\sum_{i=2}^{N'} C_i\) です。

これらをまとめると、\(f(s)\) を \(s\le 2\) なら \(s\) 、\(s>2\) なら \(s-2\) としてコストは \(\displaystyle f(N')C_1+\sum_{i=1}^{N'}C_i\) と表せます。

\(N'\) 頂点を \(k\) 個の連結成分に分けることを考えます。上記の \(k=1\) の場合より、各連結成分はそれぞれ頂点 \(1,2,\ldots,k\) を含むとして良いです。

頂点 \(i\) \((1\le i\le k)\) を含む連結成分の頂点 \(i\) 以外の頂点数を \(A_i\) とします。すると、コストは \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^k C_i f(A_i+1)\) と書くことができます。\(A_i\) の条件は \(\displaystyle A_i\geq 0, \sum_{i=1}^k A_i = N'-k\) なので、この条件下で先述の値を最小化する問題が解ければ良いです。

そして、この問題は \(N'\) と \(k\) の大小関係で場合分けすることで簡単に解くことができます。

[1] \(N'\geq 3k\) の場合

全ての \(i\) で \(A_i\geq 2\) とすることができます。したがって、\(A_1=N'-3k+2,\ A_i=2\) \((i\geq 2)\) とすればよく、この時のコストは \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^{k} C_i+(N'-3k)C_1\) です。

[2] \(N' < 3k\) の場合

いくつかの \(i\) で \(A_i\geq 2\) を満たすことができません。そのような \(i\) は \(A_i=0\) を満たすとして良く、この場合のコストは \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^{k} C_i+((N'-k)\bmod 2)C_1\) です。

[1], [2] どちらの場合も \(C\) の累積和を計算しておくことでスコアを \(O(1)\) 時間で計算することができます。したがって、\(k=1,2,\ldots,N'\) に対しスコアを計算し、それらの最小値を求めれば良いです。

以上を適切に実装することでこの問題に正答することができます。計算量はソートがボトルネックとなり \(O(N\log N)\) です。

実装例(Python3)

import sys

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    c = list(map(int, input().split()))
    c.sort()
    r = [0] * (n + 1)
    for i in range(n):
        r[i + 1] = r[i] + c[i]
    ans = 10**18
    for k in range(1, n):
        if n - 1 - k >= 2 * k:
            ans = min(ans, r[n - 1] + r[k] + (n - 1 - 3 * k) * c[0])
        else:
            ans = min(ans, r[n - 1] + r[k] + (n - 1 - k) % 2 * c[0])
    print(ans)