D. Ледяные скульптуры
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Берляндский университет готовится встретить юбилей — ему исполняется 256 лет! Специально назначенный проректор по празднованию готовится украсить университетский городок. В центре городка были воздвигнуты n ледяных скульптур. Скульптуры расположены по кругу на равном расстоянии друг от друга, то есть образуют правильный n-угольник. Они пронумерованы по порядку по часовой стрелке числами от 1 до n.

На сайте университета уже успело состояться голосование, по результатам которого каждая скульптура получила характеристику ti — степень своей привлекательности. Величины ti могут быть положительными, нулевыми или отрицательными.

Пришедший оценить работу ректор университета отметил, что, возможно, работа выполнена не идеально. Он предложил растопить некоторые скульптуры так, что:

  • оставшиеся скульптуры будут образовывать правильный многоугольник (с количеством вершин от 3 до n),
  • сумма величин ti для оставшихся скульптур будет максимальна.

Помогите проректору по празднованию произвести анализ замечания — найдите максимальное значение суммы ti, которое может быть получено таким способом. Разрешается не растапливать скульптуры вообще. Передвигать скульптуры нельзя.

Входные данные

В первой строке входных данных записано целое число n (3 ≤ n ≤ 20000) — первоначальное количество скульптур. Вторая строка содержит последовательность целых чисел t1, t2, ..., tn, ti — степень привлекательности i-ой скульптуры ( - 1000 ≤ ti ≤ 1000). Числа в строке разделяются пробелами.

Выходные данные

Выведите искомую максимальную сумму привлекательностей скульптур.

Примеры
Входные данные
8
1 2 -3 4 -5 5 2 3
Выходные данные
14
Входные данные
6
1 -2 3 -4 5 -6
Выходные данные
9
Входные данные
6
1 2 3 4 5 6
Выходные данные
21
Примечание

В первом примере наиболее оптимально оставить скульптуры через одну, то есть оставить скульптуры с привлекательностями: 2, 4, 5 и 3.