题目描述

有一个包含 $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$），在图 $G$ 上都无法从 $x$ 到 $y$ 到达。

请你求出 $s$ 中所有顶点的价值之和的最大可能值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6
1 1 1 1 1 1

输出 #1

4

输入输出样例 #2

输入 #2

6
1 2 1 3 1 6

输出 #2

8

输入输出样例 #3

输入 #3

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

输出 #3

343

说明/提示

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq A_i \leq 10^9$
• 所有输入的值均为整数

样例解释 1

可以选择 $s = \{1, 2, 3, 5\}$。

样例解释 2

可以选择 $s = \{1, 5, 6\}$。

由 ChatGPT 4.1 翻译