Problem Statement

We have a directed graph G with N vertices numbered 1 to N.
Between two vertices $i,j (1 \leq i,j \leq N, i \neq j),$ there is an edge $i \to$ j if and only if both of the following conditions are satisfied.

• i<j
• $\mathrm{gcd}(i,j)>1$

Additionally, each vertex has an associated value: the value of Vertex i is A_i.
Consider choosing a set s of vertices so that the following condition is satisfied.

• For every pair (x,y) (x<y) of different vertices in s, y is unreachable from x in G.

Find the maximum possible total value of vertices in s.

Input

Input is given from Standard Input in the following format:
N
$A_1 A_2 \cdots A_N$

Output

Print the answer.

Constraints

• $1 \leq N \leq 10^6$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Sample Input 1

6
1 1 1 1 1 1

Sample Output 1

4

We should choose s={1,2,3,5}.

Sample Input 2

6
1 2 1 3 1 6

Sample Output 2

8

We should choose s={1,5,6}.

Sample Input 3

20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

Sample Output 3

343

见题面 Input 部分

见题面 Output 部分