Берляндский университет готовится встретить юбилей — ему исполняется 256 лет! Специально назначенный проректор по празднованию готовится украсить университетский городок. В центре городка были воздвигнуты n ледяных скульптур. Скульптуры расположены по кругу на равном расстоянии друг от друга, то есть образуют правильный n-угольник. Они пронумерованы по порядку по часовой стрелке числами от 1 до n.
На сайте университета уже успело состояться голосование, по результатам которого каждая скульптура получила характеристику ti — степень своей привлекательности. Величины ti могут быть положительными, нулевыми или отрицательными.
Пришедший оценить работу ректор университета отметил, что, возможно, работа выполнена не идеально. Он предложил растопить некоторые скульптуры так, что:
- оставшиеся скульптуры будут образовывать правильный многоугольник (с количеством вершин от 3 до n),
- сумма величин ti для оставшихся скульптур будет максимальна.
Помогите проректору по празднованию произвести анализ замечания — найдите максимальное значение суммы ti, которое может быть получено таким способом. Разрешается не растапливать скульптуры вообще. Передвигать скульптуры нельзя.
Выходные данные
Выведите искомую максимальную сумму привлекательностей скульптур.
Примечание
В первом примере наиболее оптимально оставить скульптуры через одну, то есть оставить скульптуры с привлекательностями: 2, 4, 5 и 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
1 2 -3 4 -5 5 2 3
|
14
|
|
2
|
6
1 -2 3 -4 5 -6
|
9
|
|
3
|
6
1 2 3 4 5 6
|
21
|