GCD Connects

Time limit4sMemory limit1024 MB

Summary

Given n numbers, pick a spanning tree of pairs that maximizes the sum of gcd over its edges, and print that maximum sum.

Level: Medium7 of 10
Topics: Union-find, Math, Greedy
Solved: No attempts yet

Statement

A university department admitted $n$ students who do not know each other. They need a fast and reliable way to share news about upcoming exams and tests, so they will create several dialogs in a new Byteland messenger. Each dialog includes exactly two students. Information spreads like this: when a student learns about an upcoming test, they send the message to every dialog they have with their groupmates. Then every person who received the message for the first time sends it to all dialogs they take part in, and so on.

The class monitor wants to build a dialog network so that every student receives the message at least once. The number of dialogs must be as small as possible. Each student $i$ has an integer $a_i$ . The score of a dialog between students $u$ and $v$ is $\gcd(a_u, a_v)$ . The monitor wants the total score of all dialogs to be as large as possible. Find that maximum total score.

Input

The first line contains a single integer $n$ ( $1 \le n \le 100\,000$ ), the number of students. The second line contains $n$ positive integers $a_i$ ( $1 \le a_i \le 1\,000\,000$ ).

Output

Print a single integer: the maximum total score of a network that the monitor can build, given that the number of dialogs is minimal.

Hint

In the first sample, the optimal answer creates dialogs between the pairs (1, 2), (2, 3), (2, 4), (4, 5). The total score of this network is $1 + 1 + 2 + 1 = 5$ .

Examples2

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```
Example 2
Input
```
2
5 10
```
Expected output
```
5
```