题目描述

小明饿了，所以小明要去吃饭。桌子上摆了n道菜，第i道菜的编号是$i$，美味程度是$a_i$。小明可以选择从任意一道菜开始吃（也可以不吃离场）。

由于餐厅的额外要求：假设小明吃的上一道菜的编号是$x$，那么小明吃的下一道菜的编号必须是$x$的倍数。

问：小明吃到的菜的美味程度之和最多是多少。

输入格式

从文件eat.in中读入数据。

总共两行。

第一行输入$n$。

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

输出格式

输出到文件eat.out中。

一个整数，表示答案。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

7

样例 #2

样例输入 #2

5
1 -1 4 7 5

样例输出 #2

8

提示：

【​样例解释1​】

小明先吃1，再吃2，再吃4，可以得到1+2+4=7的美味程度。

【​样例解释2​】

小明先吃1，再吃4，可以得到1+7=8的美味程度。

【​数据范围​】

对于$20\%$的数据，$n \leq 20$。

对于$30\%$的数据，$n \leq 30$。

对于$60\%$的数据，$n \leq 10000$。

对于$100\%$的数据，$n \leq 2×10^5,-10^5\leq a_i \leq 10^5$。

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

来源：

2024 西安市信息学算法编程大赛小高组T4