← 返回题目列表

Codeforces · 158/D

D. 冰雕

中文机器翻译题面 查看原题

贝兰德大学准备庆祝建校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。