配点 : $800$ 点

問題文

$N$ 頂点からなる有向グラフ $G$ があり，頂点には $1$ から $N$ までの番号がついています．

二つの頂点 $i,j$ ($1 \leq i,j \leq N$, $i \neq j$) の間には，以下の条件を両方満たす時，またその時のみ，辺 $i \to j$ が存在します．

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

また，各頂点にはそれぞれ価値が定まっており，頂点 $i$ の価値は $A_i$ です．

以下の条件を満たすように頂点の集合 $s$ を選ぶことを考えます．

• $s$ に含まれるどの二つの異なる頂点の組 $(x,y)$ ($x) についても，$G$上で$x$から$y$ には到達できない．

$s$ に含まれる頂点の価値の総和としてあり得る最大値を求めてください．

制約

• $1 \leq N \leq 10^6$
• $1 \leq A_i \leq 10^9$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

出力

答えを出力せよ．

6
1 1 1 1 1 1

4

$s=\{1,2,3,5\}$ とすればよいです．

6
1 2 1 3 1 6

8

$s=\{1,5,6\}$ とすればよいです．

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

343