Minimize Effort with EffiBin Kit

In each step, choose two positions i and j; if the current effort[i] is divisible by the current effort[j], change effort[i] to effort[j]. You may do this any number of times, or not at all. The goal is to minimize the sum of the final array. The operation does not divide i by j; it replaces i directly with the current value of j.

输入格式

The first line contains n and the second line contains effort. 1≤n≤200000, 1≤effort[i]≤200000.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
3 6 2 5 25

输出：

17

样例 2

输入：

3
6 10 15

输出：

31

样例 3

输入：

3
2 4 8

输出：

6

样例说明

The answers are 17, 31 and 6 respectively. In the second example no value is divisible by any other, smaller original value, so values cannot simply become the common factor 1.