← 返回题目列表

AtCoder · arc085_c

E. 乘法

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

我们有 N 宝石标记 1 通过 N.

您可以执行以下操作任意次数(可能为零)。

  • 选择一个正整数 x,并粉碎所有标有倍数的宝石 x.

然后,对于每个 i,如果宝石标记为 i 没有被砸碎,您将收到 a_i 日元(日本的货币)。 然而, a_i 可能为负数,在这种情况下,您将被收取费用。

通过最佳执行操作,您可以赚取多少日元?

约束

  • 所有输入值均为整数。
  • 1 \leq N \leq 100
  • |a_i| \leq 10^9

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N

输出

打印可以赚取的最大金额。


示例输入 1

6
1 2 -6 4 5 3

示例输出 1

12

粉碎宝石是最佳选择 3 和 6.


示例输入 2

6
100 -100 -100 -100 100 -100

示例输出 2

200

示例输入 3

5
-1 -2 -3 -4 -5

示例输出 3

0

最好粉碎所有宝石。


示例输入 4

2
-1000 100000

示例输出 4

99000