题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

答えを出力せよ．

题目大意

构造一个图，$(i,j)$ 有边当且仅当 $i<j$ 且 $(i,j)>1$，求一个反链 $S$，使得 $\sum\limits_{i\in S}A_i$ 最大。

translated by syzf2222

6
1 1 1 1 1 1

4

6
1 2 1 3 1 6

8

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

343

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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