[ARC085C] MUL

题意翻译

有 $N$ 个宝石,编号为 $1, 2, .., N$ 你可以进行任意次以下操作(可以一次也不做) - 选择一个正整数 $x$,将所有编号为 $x$ 的倍数的宝石打碎 最后,对于每个没有被打碎的宝石 $i$,你可以获得 $a_i$ 円。要注意的是,有些 $a_i$ 是负值,这意味着你要倒贴钱。 在最好的情况下,你能获得多少円呢? ## **数据范围** 所有输入的数都是整数 $1 \leq N \leq 100$ $ |a_i| \leq 10^9$ ## **输入格式** 第一行一个整数 $N$,代表共有 $N$ 个宝石 第二行 $N$ 个整数,分别代表 $a_1, a_2, ..., a_N$ ## **输出格式** 一行一个整数,表示你最多可以得到的钱 翻译提供者:魔塔哈奇

题目描述

[problemUrl]: https://arc085.contest.atcoder.jp/tasks/arc085_c 宝石が $ N $ 個あり,それぞれ $ 1,\ 2,\ ...,\ N $ と数が書かれています。 あなたは,以下の操作を好きなだけ行うことが出来ます(一度も行わなくてもよいです)。 - 正整数 $ x $ を選ぶ。 $ x $ の倍数が書かれた宝石を全て叩き割る。 そして, $ i $ が書かれていた宝石が割られずに残っていた場合, $ a_i $ 円貰います。 ただし,この $ a_i $ は負の場合もあり,その場合はお金を払わなくてはいけません。 うまく操作を行った時,あなたは最大で何円お金を貰えるでしょうか?

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ ```

输出格式


Print the maximum amount of money that can be earned.

输入输出样例

输入样例 #1

6
1 2 -6 4 5 3

输出样例 #1

12

输入样例 #2

6
100 -100 -100 -100 100 -100

输出样例 #2

200

输入样例 #3

2
-1000 100000

输出样例 #3

99000

输入样例 #4

6
1 2 -6 4 5 3

输出样例 #4

12

输入样例 #5

6
100 -100 -100 -100 100 -100

输出样例 #5

200

输入样例 #6

2
-1000 100000

输出样例 #6

99000

说明

### 制約 - 入力は全て整数 - $ 1\ \leq\ N\ \leq\ 100 $ - $ |a_i|\ \leq\ 10^9 $ ### Problem Statement We have $ N $ gemstones labeled $ 1 $ through $ N $ . You can perform the following operation any number of times (possibly zero). - Select a positive integer $ x $ , and smash all the gems labeled with multiples of $ x $ . Then, for each $ i $ , if the gem labeled $ i $ remains without getting smashed, you will receive $ a_i $ yen (the currency of Japan). However, $ a_i $ may be negative, in which case you will be charged money. By optimally performing the operation, how much yen can you earn? ### Constraints - All input values are integers. - $ 1\ \leq\ N\ \leq\ 100 $ - $ |a_i|\ \leq\ 10^9 $ ### Sample Explanation 1 宝石 $ 3,\ 6 $ を叩き割るのが最適です。 ### Sample Explanation 3 全ての宝石を叩き割るのが最適です。 ### Sample Explanation 5 It is optimal to smash Gem $ 3 $ and $ 6 $ . ### Sample Explanation 7 It is optimal to smash all the gems.