Lost in MST

题号：NC295141
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

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 , representing the number of vertices in the graph.

The second line contains  positive integers .

输出描述:

Output a single line with a single integer, representing the total weight of the edges in the minimum spanning tree of .

示例1

输入

复制

4
7 8 9 10

输出

复制