贝兰德大学准备庆祝建校256周年!一位专门为庆祝活动任命的副校长正在准备装饰校园。校园中央竖立着精美的冰雕。这些雕塑以彼此等距离排列成一个圆圈,因此它们形成了一个规则的n边形。它们按顺时针顺序编号,编号为 1 到 n。
大学现场已经进行了投票,评估了每个雕塑的ti特征——雕塑的吸引力程度。 ti 的值可以是正值、负值或零。
当大学校长来评估工作时,他说这可能不是一个完美的安排。他建议熔化一些雕塑,以便:
- 剩余的雕塑形成正多边形(顶点数应在 3 到 n 之间),
- 剩余雕塑的 ti 值之和最大化。
帮助副校长分析批评——找出这样可以得到的ti sum的最大值。允许完全不熔化任何雕塑。雕塑不能移动。
输入
第一输入行包含一个整数 n (3 ≤ n ≤ 20000) — 雕塑的初始数量。第二行包含整数序列 t1, t2, ..., tn, ti — 第 i 个雕塑的吸引力程度 (- 1000 ≤ ti ≤ 1000)。行上的数字用空格分隔。
输出
打印所需的雕塑吸引力的最大总和。
示例
输入 #1
8 1 2 -3 4 -5 5 2 3
输出 #1
14
输入 #2
6 1 -2 3 -4 5 -6
输出 #2
9
输入 #3
6 1 2 3 4 5 6
输出 #3
21
注意
在第一个样本中,最好留下每隔一个雕塑,即留下具有吸引力的雕塑:2、4、5 и 3。