Assume for simplicity that all the integers in the array are distinct. (If there are at least two same values, we can try to take these pairs and update the answer)

Let's notice (key observation) that $$$a + b + gcd(a, b) \ge 2 \cdot max(a, b)$$$. Indeed, $$$gcd(a, b) = gcd(a, |b - a|) \le |b - a|$$$. Therefore the optimal solution always contains the maximum of the array. Otherwise we can replace the minimal chosen element with the global maximum. So you should find the maximum and test it again all other values.

Looks like $$${O}(n \cdot (\log n + \log C))$$$ due to sorting and $$$n$$$ calls of $$$gcd$$$.

Assume for simplicity that all the integers in the array are distinct. (If there are $$$cnt_x$$$ values equal to $$$x$$$, than the solution is pretty much the same, despite the fact you need to update the answer for $$$k = 1..cnt_x$$$ with $$$(k + 1)\cdot x$$$).

Let's apply somehow the key observation from the first part. One can reuse it in the following way. Let $$$a_1 < a_2 < \dots < a_k$$$ be some subset of the initial array $$$a$$$. Then $$$a_1 + \dots + a_k + gcd(a_1, \dots, a_k) \le b + a_2 + \dots + a_k$$$ where $$$b$$$ is any number greater than $$$a_2$$$. Therefore the optimal solution always contains the maximal $$$k - 1$$$ values of the array.

Sort the array in decreasing order and proceed with the following problem: we have to find for each $$$k = 2..n$$$ a number $$$a_j$$$ ($$$k \le j \le n$$$) such that it maximizes $$$a_j + gcd(a_j, g)$$$, where $$$g := gcd(a_1, \dots, a_{k - 1})$$$.

Here we come with another observation: for almost all $$$k$$$'s the $$$g$$$ is the same. Indeed, it can only decrease while $$$k$$$ increases and, provided that, it is divided by at least 2. So every time it decreases recalculate the sum of $$$a_j + gcd(a_j, g)$$$ and every time it stays the same, just take the biggest value on the suffix.

Looks like $$${O}(n \log n + n \log^2 C)$$$, hopefully it would pass :D