Calculate Minimum Cost (Divisible Resource Replacement)

You are given a positive integer array cost. Each operation chooses two positions x and y; when the current cost[x] is divisible by the current cost[y], you may set cost[x]=cost[y]. Any number of operations may be performed, including zero; find the minimum possible sum of the final elements. Values can only be copied from existing positions, and new values such as a gcd cannot be created; duplicate values count toward the sum at each of their positions. The answer 17 given for the public MDX input [3,6,2,6,25] is wrong; under the stated operation it should be 34; only the complete FastPrep input [3,6,2,5,25] has the answer 17.

输入格式

The first line contains n, and the second line contains n integers cost[i]. 1≤n≤2000000, 1≤cost[i]≤200000000.

输出格式

Output the minimum possible sum as a 64-bit integer.

样例 1

输入：

5
3 6 2 6 25

输出：

34

样例 2

输入：

5
3 6 2 5 25

输出：

17

样例 3

输入：

3
6 10 15

输出：

31

样例说明

In the first example, the two 6s become 2 and 25 cannot be lowered, so the sum is 34. In the second example, 6 becomes 2 and 25 becomes 5, so the sum is 17. In the third example, 6, 10, 15 do not divide one another, so the sum stays 31; they cannot be turned into the nonexistent gcd=1.