Suppose \(C\) is sorted in ascending order. Also, since preparing multiple cards with the same pair \((a,b)\) does not contribute to the condition, we may assume that no edge is drawn more than once between the same pair.

Consider a graph with \(N\) vertices, and associate writing \(a\) on the front and \(b\) on the back of a card with creating an undirected edge connecting vertices \(a\) and \(b\). Then, the condition can be rephrased as follows:

• The graph has at most one isolated point (a vertex of degree \(0\)).
• There is no connected component with two vertices and one edge.

To minimize the cost, it is better to have one isolated point, so we may assume that vertex \(N\) is the isolated point. From here on, consider minimizing under only the latter condition, using \(N'=N-1\) vertices.

First, consider the minimum total cost when all \(N'\) vertices are required to be connected. (Hereafter, we abbreviate “the minimum total cost” as “the cost”.)

If \(N'=1\), since there must be no isolated point, we need to create a self-loop, and the cost is \(2C_1\). Also, if \(N'=2\), since the number of edges must be at least \(2\), the cost is \(3C_1+C_2\). If \(N'\geq 3\), it is optimal to connect everything to vertex \(1\), and the cost is \(\displaystyle (N'-1)C_1+\sum_{i=2}^{N'} C_i\).

Summarizing these, letting \(f(s)\) be \(s\) if \(s\le 2\), and \(s-2\) if \(s>2\), the cost can be expressed as \(\displaystyle f(N')C_1+\sum_{i=1}^{N'}C_i\).

Consider dividing the \(N'\) vertices into \(k\) connected components. From the case \(k=1\) above, we may assume that each connected component contains one of the vertices \(1,2,\ldots,k\).

Let \(A_i\) be the number of vertices, other than vertex \(i\) itself, in the connected component containing vertex \(i\) \((1\le i\le k)\). Then, the cost can be written as \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^k C_i f(A_i+1)\). The conditions on \(A_i\) are \(\displaystyle A_i\geq 0, \sum_{i=1}^k A_i = N'-k\); it suffices to solve the problem of minimizing the above value under these conditions.

This problem can be easily solved by case-splitting on the relative sizes of \(N'\) and \(k\).

[1] Case \(N'\geq 3k\)

It is possible to set \(A_i\geq 2\) for all \(i\). Therefore, it suffices to set \(A_1=N'-3k+2,\ A_i=2\) \((i\geq 2)\), in which case the cost is \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^{k} C_i+(N'-3k)C_1\).

[2] Case \(N' < 3k\)

For some \(i\), \(A_i\geq 2\) cannot be satisfied. We may let such \(i\) satisfy \(A_i=0\), in which case the cost is \(\displaystyle \sum_{i=1}^{N'} C_i+\sum_{i=1}^{k} C_i+((N'-k)\bmod 2)C_1\).

In both cases [1] and [2], by precomputing the prefix sums of \(C\), the score can be computed in \(O(1)\) time. Therefore, it suffices to compute the score for \(k=1,2,\ldots,N'\) and find the minimum among them.

By implementing the above appropriately, this problem can be solved. The time complexity is \(O(N\log N)\), with sorting as the bottleneck.

Sample implementation (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)