题目描述

小可是一名星际探险家。太空中有 $n$ 颗行星，第 $i$ 颗行星的编号是 $i$，资源值为 $a_i$。

小可可以选择从任意一颗行星开始采集资源（也可以直接返航，不采集任何资源）。

由于飞船的跃迁引擎限制：假设小可上一次采集的行星编号是 $x$，那么下一次只能跃迁到编号恰好是 $x$ 的倍数的行星上。

问：小可采集到的资源值之和最大是多少。

输入格式

第一行输入 $n$。

第二行输入 $n$ 个整数，表示 $a_1, \dots, a_n$。

输出格式

输出一个数字表示答案。

样例

5
1 2 3 4 5

7

5
1 -1 4 7 5

8

样例解释 #1

小可先采集 $1$ 号行星（资源 $+1$），再跃迁到 $2$ 号行星（$+2$），再跃迁到 $4$ 号行星（$+4$），共获得 $1 + 2 + 4 = 7$ 点资源。

样例解释 #2

小可先采集 $1$ 号行星（资源 $+1$），再跃迁到 $4$ 号行星（$+7$），共获得 $1 + 7 = 8$ 点资源。

（$4$ 号行星的资源值为 $7$，不是 $4$，注意 $a_4 = 7$。）

数据范围

对于 $20\%$ 的数据：$n \le 20$。

对于 $30\%$ 的数据：$n \le 30$。

对于 $60\%$ 的数据：$n \le 1000$。

对于额外 $20\%$ 的数据：保证 $a_i = i$。

对于 $100\%$ 的数据：$n \le 3000$，$-10^5 \le a_i \le 10^5$。