小红地上划分了n个格子，按1~n编号，并在每个格子上写上了一个数字表示格子的得分，她要从起始节点1开始从编号小的格子往编号大的格子跳。

她的跳远水平很高，她从任何位置跳一步内都能跳到任意一格编号更大的格子上。

小明虽然不擅长跳跃，但是他的数学很好，于是他对小红说：“你可以从任意位置出发，也可以从任意位置结束，但是每次跳的格子编号必须和之前的所有经过的格子编号（两两）互质。” (即gcd(a,b)=1)

小红一下子就懵逼了，她的数学不是很好，你可以帮帮她吗？在小明的规则下，使得她的跳房子的总分最大。

从文件jump.in中读入数据。输入第一行仅一个数字n，表示格子的数量。

输出第二行包含n个正整数，第i个数字a_i表示第i格跳到后的得分。

输出到文件jump.out中。输出仅一行，是最大的得分。

样例1选择跳跃的格子编号顺序为{1,5,7,8,9}，得分为1+5+7+8+9=30。

样例2选择跳跃的格子编号顺序为{1,2,3,5,7}，得分为10+9+8+6+4=37。

样例3选择跳跃的格子编号顺序为{1,3,10}，得分为 2+6+100=108。

0 < n\le150,\ {0\le a}_i\le 10000

原创