I recently gave a coding round of Adobe on unstop which had the following problem I can't solve: Given an array $$$x$$$ of $$$N$$$ elements and an empty array $$$y$$$. You can remove any element from $$$x$$$ and transfer it to $$$y$$$. You can also choose any element $$$a$$$ from $$$x$$$ and $$$b$$$ from $$$y$$$ and add $$$GCD(a, b)$$$ to $$$score$$$ and then you have to remove $$$a$$$ from $$$x$$$ and transfer it to $$$y$$$ while $$$b$$$ stays in $$$y$$$. You can perform both operations until $$$x$$$ is not empty. Report the maximum $$$score$$$ if you play optimally.

$$$1 \lt = N \lt = 1e4$$$
$$$1 \lt = x[i] \lt = 1e4$$$
Example
Input
N = 5
x = 2 3 4 1 6
Output
8

First delete 6 from x. Now x = [2 3 4 1], y = [6]. Select 3 and 6 then score becomes gcd(3,6) = 3 and x = [2 4 1], y = [6 3]. Choose 4 and 6, score is 3+gcd(4,6)=5, x = [2 1] y = [6 3 4]. Choose 2 and 4, score is 5+2=7. Choose 1 and 2, score is 7+1=8.

Input
N = 4
x = 1 2 3 4
Output
4
Any help is appreciated.