给定一个序列 $a$ ，定义其权值为： $$ \sum_{i=1}^n\gcd(a_1,a_2,...,a_i) $$ 现在你可以重排 $a$ ，求这个权值的最大值。

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the size of the array $ a $ . The second line contains $ n $ integers $ a_{1}, \, a_{2}, \, \dots, \, a_{n} $ ( $ 1 \le a_{i} \le 5 \cdot 10^6 $ ) — the array $ a $ .

Output the maximum value of the function that you can get by reordering elements of the array $ a $ .

In the first example, it's optimal to rearrange the elements of the given array in the following order: $ [6, \, 2, \, 2, \, 2, \, 3, \, 1] $ : $$ \operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4)\\ + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6)\\= 6 + 2 + 2 + 2 + 1 + 1 = 14. $$ It can be shown that it is impossible to get a better answer. In the second example, it's optimal to rearrange the elements of a given array in the following order: $[100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54]$.

CF1614D1