One day, Colin got lost in a complete undirected graph $$$G$$$ with $$$n$$$ vertices, and each vertex $$$i$$$ is associated with a magic parameter $$$c_i$$$. For each pair of vertices $$$(i,j)$$$, there exists an undirected edge connecting them with weight $$$w_{i,j} = \gcd(c_i, c_j) + \text{lcm}(c_i, c_j)$$$.
Can you find the graph's minimum spanning tree $$$G$$$ to save Colin?
Recall that $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$, and $$$\text{lcm}(x, y)$$$ is the least common multiple of $$$x$$$ and $$$y$$$.
The first line contains a single integer $$$n~(1\le n\le 10^5)$$$, representing the number of vertices in the graph.
The second line contains $$$n$$$ positive integers $$$c_1,c_2,\cdots,c_n~(1\le c_i\le 10^6)$$$.
Output a single line with a single integer, representing the total weight of the edges in the minimum spanning tree of $$$G$$$.
47 8 9 10
163
