题目描述

给定一个有 $N$ 个顶点的有向图 $G$，顶点编号为 $1$ 到 $N$。

对于两个顶点 $i,j$（$1 \\leq i,j \\leq N$，$i \\neq j$），当且仅当满足以下两个条件时，存在一条从 $i$ 到 $j$ 的有向边 $i \\to j$。

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

此外，每个顶点都有一个相关联的值：顶点 $i$ 的值为 $A_i$。

考虑选择一个顶点集合 $s$，使得满足以下条件。

• 对于 $s$ 中两个不同的顶点 $(x,y)$（$x<y$），$y$ 在 $G$ 中无法从 $x$ 到达。

找出 $s$ 中顶点的最大可能总值。

约束条件

• $1 \\leq N \\leq 10^6$
• $1 \\leq A_i \\leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入读入数据。

输入的格式如下：

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

输出

输出答案。

示例输入 1

6
1 1 1 1 1 1

示例输出 1

4

我们应该选择 $s=\\{1,2,3,5\\}$。

示例输入 2

6
1 2 1 3 1 6

示例输出 2

8

我们应该选择 $s=\\{1,5,6\\}$。

示例输入 3

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

示例输出 3

343